#include #pragma GCC target ("avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include using namespace std; using mint = atcoder::modint998244353; // TLE int main() { int h,w; cin >> h >> w; vector s(h); for (int i=0; i> s[i]; vector dp(h, vector(h, mint(0))); dp[0][0] = 1; // dp[i][j][k]: i列目まで決めて、Aliceがその列で到達した最大の行がj、Bobがその行で到達した最小の行がk // 遷移は累積和で高速化しない場合、O(H^3W) for (int i=1; i(h, mint(0))); for (int j=0; j 0 && dpn[j-1][k].val() != 0) dpn[j][k] += dpn[j-1][k]; for (int l=k; l>=0; l--) { if (s[l][i-1] == '#') break; if (dp[j][l].val() != 0) dpn[j][k] += dp[j][l]; } } swap(dp, dpn); } cout << dp[h-2][h-1].val() << '\n'; }