ARC196 B. Torus Loop
Difficulty:None
問題
縦線が入ったタイルと斜め線が入ったタイルがある。H×Wのマスそれぞれにどちらを置くかだけ決まっているので向きを決めたい。トーラスに見立てて、線が行き止まりを持たないような向き付けの方法は何通りか。
解法
斜め線のタイルについては、上下と左右を独立に選べると考えてよい。縦線のタイルはそういうことはできないので困る。
斜め線のタイルの向きを一個決めると、同じ列/行にあるタイルの向きが色々と決まる。これを少し考えると、同じ行/列にある斜め線のタイルの個数は偶数でなければならないことがわかる。
縦線の関係で、縦だった時に横になってほしいとか縦になってほしいみたいなのがある（語彙力）。同じであってほしいやつは重み0、違う向きであってほしいときは重み1として、H+Wのグラフを作り、重み付き二部グラフになっていたら、それの連結成分数が答え。
実装
連結成分数は通常のUFで求め、重み付き二部グラフの矛盾判定は普通にBFSしている。
code:cpp
void slv(){
int h,w;cin >> h >> w;
vector<string>s(h);
for(auto&i:s)cin >> i;
dsu uf(h+w);
rep(i,0,h)rep(j,0,w)if(sij=='B')uf.merge(i,j+h); rep(i,0,h){
int cnt{};
rep(j,0,w){
}
if(cnt%2==1){
O(0);
return;
}
}
rep(j,0,w){
int cnt{};
rep(i,0,h){
}
if(cnt%2==1){
O(0);
return;
}
}
vector dp1(h,vector(w,0));
vector dp2(h,vector(w,0));
rep(i,h){
ll now{};
rep(j,w){
}
}
rep(j,w){
ll now{};
rep(i,h){
}
}
vector<vector<pair<ll,ll>>>g(h+w);
rep(i,h){
rep(j,w){
}
}
}
//二部グラフ判定
{
vector<ll>col(h+w,-1);
queue<ll>q;
rep(i,h+w){
q.push(i);
while(q.size()){
ll pos = q.front();q.pop();
q.push(to);
}
O(0);
return;
}
}
}
}
}
}
int cnt = size(uf.groups());
int ans = 1;
for(;cnt--;){
ans *= 2;
ans %= 998244353;
}
O(ans);
}
bool solve(){
LL(t);for(;t--;)slv();
return true;
}