题目是一个很像 NIM 博弈的一道 dp 问题, 实际上就是利用了 NIM 博弈的结论, XOR 为 0
原题目的意思是给定 n 堆石头, 可以取走 0-d 堆石头, 问取走之后后手必胜 (实际上就是 xor 为 0 的情况) 的取法数目
就是利用 dp, 状态表示就是前 i 堆, 取走 j 堆, xor 值为 k
初始化的的状态就是 dp[i,0,0]=1;
转移方程为 dp[i,j,k]=dp[i-1,j,k]+dp[i-1,j-1,k^val[i]];
也就是由第 i 堆不取产生 k 的情况, 和第 i 堆取走之后前 i-1 堆 k^val[i] 的值
计算所有堆的抑或值, 这样取出来的堆只需要值为 sum 就相当于取走直接剩下的抑或值为 0
最后只需要计算 dp[n][i][sum] 的值, i∈[0,d], 其中 i=0 的情况等价于 sum=0 的情况, 直接处理
- #include
- #include
- #include
- const int MOD=(int)1e9+7;
- int dp[1001][12][1030];
- int num[1005];
- int main(){
- int T;
- std::cin>>T;
- while(T--)
- {
- memset(dp,0,sizeof(dp));
- int n,d;
- scanf("%d%d",&n,&d);
- int sum=0;
- for(int i=1;i<=n;i++)
- {
- scanf("%d",&num[i]);
- sum^=num[i];
- }
- for(int i=0;i<=n;i++)
- {
- dp[i][0][0]=1;
- }
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=d;j++)
- {
- for(int k=0;k<=1023;k++)
- {
- dp[i][j][k]=(dp[i-1][j][k]+dp[i-1][j-1][k^num[i]])%MOD;
- }
- }
- }
- int ans=0;
- for(int i=1;i<=d;i++)
- {
- ans=(ans+dp[n][i][sum])%MOD;
- }
- if(sum==0) ans++;
- printf("%d\n",ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3012950.html