Boxes and Stones - UVa 12525 dp

題意：有n個小球，m個盒子，小球被配置設定到1到m-1的盒子中，每次P標明其中的一部分小球，C可以選擇保留或不保留標明的球，若保留，這些球都向移動到其右邊的盒子，剩下的剔除，反之亦然。如果有球到m盒子時P就赢了。問C赢的話，開局的方式有多少種。

思路：如果一種局面使得C必勝時，從左往右計數球的個數，将每個盒子中的球數除以2，折算到它右邊的盒子中，最終使得m盒子沒有球的情況，就是C必勝的情況。這個想法是從4 1 0 和4 2 0 這種情況考慮發現的。

          dp[m][n][k]表示到第m個格子，用了n個球，且第m個格子折算後的數為k的情況數量。

AC代碼如下：

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
ll dp[110][210][410],MOD=1e9+7;
int main()
{ int i,j,k,n,m;
  dp[0][0][0]=1;
  for(i=1;i<=100;i++)
   for(j=0;j<=200;j++)
   { dp[i][j][0]=(dp[i-1][j][0]+dp[i-1][j][1])%MOD;
     for(k=0;k<=200;k++)
      dp[i][j][k]=(dp[i][j-1][k-1]+dp[i-1][j][k*2]+dp[i-1][j][k*2+1])%MOD;
   }
  while(~scanf("%d%d",&n,&m))
   printf("%lld\n",dp[m][n][0]);
}