1169 石子游戏
题目来源： Interviewstreet
基准时间限制：1 秒 空间限制：131072 KB 分值: 320 难度：7级算法题
收藏
关注
有N堆石子（N <= 100)，每堆数量不超过10^9，A B两个人玩Nim游戏。Nim游戏的规则如下：A B两个人轮流拿石子，A先拿。每次只能从一堆中取若干个，可将一堆全取走，但不可不取，拿到最后1颗石子的人获胜。在A B开始游戏之前，你可以先做些手脚，从任意多堆取任意多石子使得A必败。但至少有一堆石子的数量不变。问有多少种不同的改变的方法？由于方案数量巨大，输出Mod 10^9 + 7的结果。
Input
第1行：1个数N(2 <= N <= 100)。 第2 - N + 1行：对应石子的数量C[i](1 <= C[i] <= 10^9)
Output
输出方案数量Mod 10^9 + 7的结果
Input示例
3 246 638 355
Output示例
602
数位DP+思路~
题目要求至少有一堆没有取，那么先不管这个限制DP一遍，再把所有堆都取出一个，再不管限制DP一遍，前面的减去后面的就是答案，所以这个问题转化为无限制的。
我们枚举从位k开始改变，（k位一定改变），用f[i][j]表示第i个数，目前i位是0，DP即可。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define ll long longconst int mod=1e9+7;int n,a[102],mi[30],f[102][2],ans;void add(int &a,int b)
{a=a+b>=mod ? a+b-mod:a+b;
}int cal()
{int ans=0,kkz,now;for(int k=29;~k;k--){memset(f,0,sizeof(f));f[0][0]=1;for(int i=1;i<=n;i++)if(a[i]&mi[k]){f[i][0]=(ll)f[i-1][0]*mi[k]%mod+(ll)f[i-1][1]*(a[i]%mi[k]+1)%mod;f[i][1]=(ll)f[i-1][1]*mi[k]%mod+(ll)f[i-1][0]*(a[i]%mi[k]+1)%mod;}else{f[i][0]=(ll)f[i-1][0]*(a[i]%mi[k]+1)%mod;f[i][1]=(ll)f[i-1][1]*(a[i]%mi[k]+1)%mod;}kkz=0;now=1;for(int i=n;i;i--){if(a[i]&mi[k]) add(ans,(ll)f[i-1][kkz]*now%mod);kkz^=(a[i]&mi[k])>0;now=(ll)now*(a[i]%mi[k]+1)%mod;}if(kkz){ans++;break;}}return ans-1;
}int main()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);mi[0]=1;for(int i=1;i<=29;i++) mi[i]=mi[i-1]<<1;ans=cal();for(int i=1;i<=n;i++) a[i]--;ans=(ans-cal()+mod)%mod;printf("%d\n",ans);return 0;
}