JOI 2009 春合宿 day2-1 「abduction」

縦方向と横方向でそれぞれ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;
}