[JOI合宿]2009-Day2:Abduction

ローカルでAC確認済み.
明らかに, 東西の移動と南北の移動は独立なので切り離して考える.
ある方向から地点Pに行くには, その方向であって、Pより前の点にいく方法すべての総和となる. ゆえに, 総和を求めて加算すれば良い.
ただし, 最初の地点については, 後ろの場所がないので, たどり着く方法は0となる.

計算量は, O(N * max(W, H))となる. 10^7って大丈夫なんだろうか...

#include <cstdio>
#include <cstring>

using namespace std;

#define MOD (10000000)

typedef long long ll;

int main(void)
{
    int W, H;
    int N;
    int dir;
    char route[10002];
    ll combx[1024], comby[1024];
    ll carry;
    
    scanf("%d%d", &W, &H);
    scanf("%d", &N);
    scanf("%s", route);
    
    memset(combx, 0, sizeof(combx));
    memset(comby, 0, sizeof(comby));
    combx[0] = comby[0] = 1;
    dir = (route[0] == 'L');
    
    for (int i = 0; i < N + 1; i++){
        carry = 0;
        
        switch (dir){
          case 0: //North
            for (int j = 0; j <= H; j++){
                carry = (carry + comby[j]) % MOD;
                comby[j] = (carry - comby[j] + MOD) % MOD;
            }
            break;
          
          case 1: //East
            for (int j = 0; j <= W; j++){
                carry = (carry + combx[j]) % MOD;
                combx[j] = (carry - combx[j] + MOD) % MOD;
            }
            break;
          
          case 2: //South
            for (int j = H; j >= 0; j--){
                carry = (carry + comby[j]) % MOD;
                comby[j] = (carry - comby[j] + MOD) % MOD;
            }
            break;
          
          case 3: //West
            for (int j = W; j >= 0; j--){
                carry = (carry + combx[j]) % MOD;
                combx[j] = (carry - combx[j] + MOD) % MOD;
            }
            break;
        }
        
        if (route[i] == 'R'){
            dir = (dir + 1) % 4;
        }
        else {
            dir = (dir + 3) % 4;
        }
    }
    
    printf("%lld\n", combx[W] * comby[H] % MOD);
    
    return (0);
}