TopCoder SRM498 Div1Hard
今日の問題。
問題
きつねが原点にいる。今、(Tx, Ty)に移動しようとしている。きつねは、1回のジャンプで、x方向の正方向に0マスからMxマス、y方向の正方向に0マスからMyマス動ける。動く距離は正でないといけない。また、bがbadに含まれるとき、x方向、y方向両方にbマス動くことはできない。badには10の倍数だけが入っている。ちょうどR回で目的地につく場合の数を求めよ。
方針
まず、ゼロ距離移動が許されてないのはうざいのでbadに0を追加してゼロ距離移動も特別視しないようにする。
次に、badを許可して、R回で(x, y)に移動する場合の数は、X方向とY方向に独立なので、DPを使うと簡単に求まる。i回badを使うと決めた場合の場合の数は、DPを使うと各「badで移動した距離の合計」ごとに「それに対するbadでの移動の仕方の場合の数」が求まるので、これに「R-i回で(x, y)に移動する場合の数」と「C(R, i)」を掛けてやればよい。あとは包除原理で一発。
コード
#include <cstdio> #include <vector> #include <algorithm> using namespace std; #define MOD 10007 class FoxJumping { int C[1601][1601]; int dpsubX[1601][801], dpsubY[1601][801]; int dp[2][81]; public: int getCount(int Tx, int Ty, int Mx, int My, int R, vector<int> bad) { for(int i=0;i<1601;i++){ C[0][i] = 0; } C[0][0] = 1; for(int i=1;i<1601;i++){ C[i][0] = 1; for(int j=1;j<1601;j++){ C[i][j] = C[i-1][j-1] + C[i-1][j]; C[i][j] %= MOD; } } bad.push_back(0); for(int i=0;i<=min(Tx/10,Ty/10);i++){ dp[0][i] = dp[1][i] = 0; } int t = 0; dp[t][0] = 1; //dpsub for(int i=0;i<=Tx;i++){ dpsubX[0][i] = 0; } dpsubX[0][0] = 1; for(int i=1;i<=R;i++){ int sum = 0; for(int j=0;j<=Tx;j++){ sum += dpsubX[i-1][j]; if(j-Mx-1>=0) sum -= dpsubX[i-1][j-Mx-1]; dpsubX[i][j] = sum%MOD; } } for(int i=0;i<=Ty;i++){ dpsubY[0][i] = 0; } dpsubY[0][0] = 1; for(int i=1;i<=R;i++){ int sum = 0; for(int j=0;j<=Ty;j++){ sum += dpsubY[i-1][j]; if(j-My-1>=0) sum -= dpsubY[i-1][j-My-1]; dpsubY[i][j] = sum%MOD; } } int ret = 0; for(int i=0;i<=R;i++){ int tmp = 0; for(int j=0;j<=min(Tx/10,Ty/10);j++){ //printf("%d %d %d\n", t, j, dp[t][j]); tmp += ((dp[t][j] * dpsubX[R-i][Tx-j*10]) % MOD) * dpsubY[R-i][Ty-j*10]; tmp %= MOD; } tmp = (tmp * C[R][i]) % MOD; if(i%2==0) ret += tmp; else ret -= tmp; ret = (ret + MOD) % MOD; for(int j=0;j<=min(Tx/10,Ty/10);j++){ dp[1-t][j] = 0; for(int k=0;k<bad.size();k++){ if(j>=bad[k]/10){ dp[1-t][j] = (dp[1-t][j] + dp[t][j-bad[k]/10]) % MOD; } } } t = 1-t; } return ret; } };