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;
  }
};