縦方向と横方向でそれぞれDPして、後で掛け合わせる。
結構ややこしい。
#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; const int mod = 10000000; int dp[2][1001]; int main(){ int w[2], n, o = 0, p = 1, q = 1; char a; scanf("%d%d%d %c",&w[0],&w[1],&n,&a); if(a == 'R') swap(o,p); for(int i = 0; i <= 1; i++) for(int j = 1; j <= w[i]; j++) dp[i][j] = 1; for(int i = 1; i < n; i++){ scanf("%c",&a); q = (o ^ (a=='L'))?-q:q; if(q>0){ for(int j = 1; j < w[o]; j++) dp[o][j] = (dp[o][j] + dp[o][j-1]) %mod; for(int j = w[o]; j >= 1; j--) dp[o][j] = dp[o][j-1]; dp[o][0] = 0; }else{ for(int j = w[o]-1; j >= 0; j--) dp[o][j] = (dp[o][j] + dp[o][j+1]) %mod; for(int j = 0; j < w[o]; j++) dp[o][j] = dp[o][j+1]; dp[o][w[o]] = 0; } swap(o,p); } ll x = dp[0][w[0]], y = dp[1][w[1]]; printf("%lld\n",x*y%mod); return 0; }