JOI 合宿 abduction

DPでし。まず、証言から、どの向きにどういう順番で進んだかが割り出せる。
その後、X成分とY成分に分解。ごにょごにょ

int w,h,n;
char angle[10005];
int mod=10000000;
int main(){
	FILE* fp=fopen("out.txt","w");
	scanf("%d%d%d",&w,&h,&n);
	vi yoko,tate;
	scanf("%s",angle);
	int cur=0;
	if(angle[0]=='R') {
		tate.pb(1);
		cur=3;
	}else {
		yoko.pb(1);
		cur=0;
	}
	REP(i,n){
		if(angle[i]=='R') cur=(cur+1)%4;
		else cur=(cur+3)%4;
		if(cur==0) yoko.pb(1);
		else if(cur==1) tate.pb(-1);
		else if(cur==2) yoko.pb(-1);
		else tate.pb(1);
	}
	int n2=yoko.size(),n3=tate.size();
	vi dp(w+1),nxt=dp;dp[0]=1;
	REP(i,n2){
		int sum;
		if(yoko[i]==1){
			sum=dp[0];
			nxt[0]=0;
			REPN(j,w+1,1) {
				nxt[j]=sum;
				sum+=dp[j];
				if(sum>=mod) sum-=mod;
			}
		}else{
			sum=dp[w];
			nxt[w]=0;
			for(int j=w-1;j>=0;--j){
				nxt[j]=sum;
				sum+=dp[j];
				if(sum>=mod) sum-=mod;
			}
		}
		dp=nxt;
	}
	lint res=dp[w];
	dp.clear();dp.resize(h+1);fill(ALL(dp),0);nxt=dp;dp[0]=1;
	REP(i,n3){
		int sum;
		if(tate[i]==1){
			sum=dp[0];
			nxt[0]=0;
			REPN(j,h+1,1){
				nxt[j]=sum;
				sum+=dp[j];
				if(sum>=mod) sum-=mod;
			}
		}else{
			sum=dp[h];
			nxt[h]=0;
			for(int j=h-1;j>=0;--j){
				nxt[j]=sum;
				sum+=dp[j];
				if(sum>=mod) sum-=mod;
			}
		}
		dp=nxt;
	}
	res=(res*dp[h])%mod;
	fprintf(fp,"%d\n",(int)res);
	return 0;
}

なんかid:tozangezanにグラフ得意キャラを形成されつつあるけどなんかDPの方が好きな気がしてきた