2回連続大ポカをやらかさなくてよかった。
https://community.topcoder.com/stat?c=problem_statement&pm=17697
問題
座標(X,Y)が与えられる。
2次元座標上で、1だけX座標を増やすか1だけY座標を増やすかいずれかの処理を繰り返し、原点から(X,Y)に移動する経路を考える。
同じ処理をちょうど3回だけ繰り返す手順が含まれていてはならない。
そのような経路は何通りか。
解法
以下のいずれでも解けるようだ。
- 上または右の移動回数を1,2,3,4回以上のいずれであるか状態を保持しながらDP
- 累積和を使い、上→右→上→右→…と交互に移動する経路を列挙する。ただし、ちょうど3回の移動分については累積和から減算しておく。
const ll mo=1000000007; ll dp[1010][1010][8]; // 1234+ 1234+ class Never3Steps { public: int count(int X, int Y) { ZERO(dp); dp[0][0][0]=1; dp[1][0][0]=1; dp[0][1][4]=1; int y,x; FOR(y,1005) FOR(x,1005) if(y+x) { // up (dp[y+1][x][0]+=dp[y][x][4]+dp[y][x][5]+dp[y][x][7])%=mo; (dp[y+1][x][1]+=dp[y][x][0])%=mo; (dp[y+1][x][2]+=dp[y][x][1])%=mo; (dp[y+1][x][3]+=dp[y][x][2]+dp[y][x][3])%=mo; //right (dp[y][x+1][4]+=dp[y][x][0]+dp[y][x][1]+dp[y][x][3])%=mo; (dp[y][x+1][5]+=dp[y][x][4])%=mo; (dp[y][x+1][6]+=dp[y][x][5])%=mo; (dp[y][x+1][7]+=dp[y][x][6]+dp[y][x][7])%=mo; } ll ret=0; ret+=dp[X][Y][0]+dp[X][Y][1]+dp[X][Y][3]+dp[X][Y][4]+dp[X][Y][5]+dp[X][Y][7]; return ret%mo; } }
まとめ
250ptでも良い気がするが…。