コンテスト中全然わからなかった．
かなり多くの人が通していてショックを受けたので記事にしました．
冷静になって翌日に考察しなおしたら解けたけど，このぐらいはサラっと考察したいところ．
問題概要
$ N $ 行 $ M $ 列のボードが与えられる．ボードの各マスは黒か白で塗られている．
白いマスを赤か青に塗ることを考える．
ここで，以下のようにドミノ（ $ 1 \times 2 $ のパーツ）を置くことを考える．
- 横に連続した $ 2 $ マスが両方とも赤なら，その $ 2 $ マスにまたがってドミノを置ける．
- 縦に連続した $ 2 $ マスが両方とも青なら，その $ 2 $ マスにまたがってドミノを置ける．
- $ 1 $ つのマスに $ 2 $ つ以上のドミノを重ねて置くことはできない．
塗った後の盤面の価値を，その盤面に置けるドミノの数の最大値とする．
全ての塗り方に対して，盤面の価値の総和を求めよ．
ただし答えが大きくなる可能性があるので， $ 998244353 $ で割った余りを答えよ．
制約
- $ 1 \leq N,M \leq 3 \times 10^{5} $
- $ NM \leq 3 \times 10^{5} $
考察
当然ながら白のマスの塗り方を全て試すのは最悪 $ O(2^{NM}) $ の時間計算量がかかるので無理である．
こういう問題は塗り分けた盤面単位で値を足していくという方針は難しく，筋が悪い．
ドミノ $ 1 $ つの価値の総和に対する寄与を考える．
まず重複など何も考えずにドミノの寄与を考える．
ドミノを置く隣接 $ 2 $ マスを全探索する．両方とも白いマスでなくてはならない．
下の図の左のように隣接 $ 2 $ マスに着目してやると，その $ 2 $ マスは所定の色で塗られることが確定する．
その他の白いマスはそれぞれ $ 2 $ 通りの塗り方が存在するため，図の例なら $ 2^{5} $ 通りの塗り分けの時にその位置にドミノを置けることがわかる．
これを足し上げることで求められるのはすべての白マスの塗り分け方に対してすべてのドミノの置き方を考えたときに置いたドミノの総和である．
この値はほぼほぼ求める価値の総和と一致しない．というのも，$ 1 $ つの塗り分けに対して $ 2 $ 通り以上のドミノの置き方がある時に重複して数えてしまうためである．
左の 2 つのドミノの寄与を単純に考えると，右の盤面に対して 2 通り数えることになる
重複，すなわち $ 1 $ つの塗り分けに対して複数のドミノの置き方がある場合について考える．
ある塗り分けられた盤面に対して，横向きにドミノを置いていたとする．
同じ領域を使って縦向きのドミノに置き換えるということは当然不可能である．
これは，赤に塗られた領域には縦向きのドミノを置くことができないためである．
したがって，横向きのドミノの置き方を考える時はそのドミノが置かれている行のみについて考えれば良い．
さらに言えば間に黒マスが挟まっても，その前後は配置について影響を及ぼさないため連続する白マスの列について考えれば良い．
これは縦のドミノと列についても同じことが言える．
以上のことから $ 1 $ 次元の問題について考えれば良いことがわかる．
重複なく数え上げるテクニックの $ 1 $ つとして条件を付けて数え上げることで重複を防ぐというものがある．
これはどうやら競技プログラミングの数え上げ典型らしく，しばしば問われる．
よくあるのは（というか殆どこれな気がするが），最左のもののみを数え上げるというものだ．
今回の問題では，左から（上から）貪欲にドミノを配置する置き方をするときのドミノの寄与のみを考えることにする．
例えば，下の図の例では赤く塗ったマスが $ 5 $ つ並んでいるためドミノの配置は複数存在するが，太線のようなドミノの置き方しかしないものと考える．
横向きのドミノ 2 個の置き方は 3 通りあるが左から貪欲に詰めたときのドミノの寄与だけを考える
連続する白いマスの列について左から $ 1, 2, \cdots $ のように番号を振って考える．
$ i-1 $ と $ i $ 番目のマスにまたがって置かれるドミノに着目したときに，そのドミノの寄与について考える．
貪欲に左から詰めたときの寄与のみを考えるため，ドミノのすぐ左側には偶数個（$ 0 $ 個も可能）連続している赤いマスがなくてはならない．それ以外はどちらの色で塗っても構わない．
このような塗り方を愚直に計算すると，各ドミノに対して左側の赤の個数を全探索するため，全体で $ O(M^{2}) $ （縦の場合は $ O(N^{2}) $ ）かかってしまい今回の制約では間に合わない．
着目するドミノと数え上げるパターン
しかしよく考えると，すぐ左の赤の個数が $ 2 $ 個以上の場合については，$ i-3 $ と $ i-2 $ にまたがるドミノの寄与を計算する際に求めている．
具体的には，左の赤の個数が $ k $ 個の場合は $ i-3 $ と $ i-2 $ にまたがるドミノにおける左の赤の個数が $ k-2 $ 個の時に対応する．
よって遷移が $ O(1) $ の DP で求めることができ，すべての寄与を最悪 $ O(N) $ や $ O(M) $ で計算することができる．
注意点としては，他の行や列の白マスも自由に塗っていいことを考慮しながら $ 1 $ つ $ 1 $ つのドミノの寄与を足し上げていくことにより，プログラム全体で $ O(NM) $ で価値の総和を計算することができた．
個人的ポイント
- この手の盤面を決めて盤面のスコアを足し上げる問題はそのままでは筋が悪い．
- スコアに寄与する単位（今回はドミノ）について，その寄与を考えると良い．
- 問題文を冷静に読むと同じ行/列，さらに連続する白マスの列についてのみ考えれば良い．
- 重複を防ぐテクニックとして，条件付きのものを数え上げるというものがある．
- 最左の要素，最左のマッチング…などなどを考えることが多い．
- ABC171 F - Strivore とか ARC114 C - Sequence Scores などよく出題されている．
- $ 2 $ 個ずつ伸びていくような数え上げは，DP で次元が落ちる．
- 別に偶数個ずつではなく一般の自然数 $ N $ にしても同じ（だと思う）．
提出URL
▶ソースコードを展開
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define ins insert
#define debug(a) cerr<<(a)<<endl
#define dbrep(a,n) rep(_i,n) cerr<<(a[_i])<<" "; cerr<<endl
#define dbrep2(a,n,m) rep(_i,n){rep(_j,m) cerr<<(a[_i][_j])<<" "; cerr<<endl;}
using namespace std;
template<class A, class B>
ostream &operator<<(ostream &os, const pair<A,B> &p){return os<<"("<<p.fi<<","<<p.se<<")";}
template<class A, class B>
istream &operator>>(istream &is, pair<A,B> &p){return is>>p.fi>>p.se;}
template<class T>
vector<T> make_vec(size_t a){
return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
const uint_fast64_t MOD = 998244353;
class mint
{
private:
using Value = uint_fast64_t;
Value n;
public:
mint():n(0){}
mint(int_fast64_t _n):n(_n<0 ? MOD-(-_n)%MOD : _n%MOD){}
mint(const mint &m):n(m.n){}
friend ostream& operator<<(ostream &os, const mint &a){
return os << a.n;
}
friend istream& operator>>(istream &is, mint &a){
Value temp; is>>temp;
a = mint(temp);
return is;
}
mint& operator+=(const mint &m){n+=m.n; n=(n<MOD)?n:n-MOD; return *this;}
mint& operator-=(const mint &m){n+=MOD-m.n; n=(n<MOD)?n:n-MOD; return *this;}
mint& operator*=(const mint &m){n=n*m.n%MOD; return *this;}
mint& operator/=(const mint &m){return *this*=m.inv();}
mint& operator++(){return *this+=1;}
mint& operator--(){return *this-=1;}
mint operator+(const mint &m) const {return mint(*this)+=m;}
mint operator-(const mint &m) const {return mint(*this)-=m;}
mint operator*(const mint &m) const {return mint(*this)*=m;}
mint operator/(const mint &m) const {return mint(*this)/=m;}
mint operator++(int){mint t(*this); *this+=1; return t;}
mint operator--(int){mint t(*this); *this-=1; return t;}
bool operator==(const mint &m) const {return n==m.n;}
bool operator!=(const mint &m) const {return n!=m.n;}
mint operator-() const {return mint(MOD-n);}
mint pow(Value b) const {
mint ret(1), m(*this);
while(b){
if (b & 1) ret*=m;
m*=m;
b>>=1;
}
return ret;
}
mint inv() const {return pow(MOD-2);}
};
int main(void)
{
cin.tie(0);
ios::sync_with_stdio(false);
int N,M; cin>>N>>M;
vector<string> f(N);
rep(i,N) cin>>f[i];
int w=0;
rep(i,N)rep(j,M){
if (f[i][j]=='o') w++;
}
vector<mint> d2(N*M+1);
d2[0]=1;
rep(i,N*M) d2[i+1]=d2[i]*2;
vector<mint> dp(max(N,M)+1);
FOR(i,2,max(N,M)){
dp[i] = dp[i-2]+d2[max(i-3,0)];
}
mint ans=0;
rep(i,N){
const auto &row = f[i];
int cnt=0;
rep(j,M){
if (row[j]=='o') cnt++;
else cnt=0;
ans+=dp[cnt]*d2[w-cnt];
}
}
rep(j,M){
int cnt=0;
rep(i,N){
if (f[i][j]=='o') cnt++;
else cnt=0;
ans+=dp[cnt]*d2[w-cnt];
}
}
cout<<ans<<"\n";
return 0;
}
