计蒜客 ICPC南京网络赛 The Great Nim Game（线性基）
发布时间
阅读量：
阅读量
大致题意：Nim游戏，是指有n堆石子，每堆石子有ai个石子，两个人轮流取，每次可以取一堆的至少一个石子，最后取不的人输。现在告诉你总共有N堆石子，这个N很大，可以有10^10000000这么大，然后每一堆的石子数量有一个产生式。你的任务是在这N堆石子中，任意选取几堆石子，使得先手必胜，问方案数。
首先，根据定理，Nim游戏要使得先手必胜，必须要所有堆的石子数量的异或和不为0。那么现在要求是使得先手必胜的方案数，我们可以考虑用总方案数2^N减去一些异或和为0的方案数。然后这里的产生式：
可以看出，最坏情况下，这里总共只会有K+1个数字。所以不用害怕可以选择的数字太多。注意到我要求的是异或和为0的方案数，异或和我们容易想到用线性基求解。对于这个N个数字，实际最多K+1种数字，我们建立线性基，不妨设这个基的基底数量为x。根据线性基的性质，所有的数字一定可以表示为这x个数字的线性组合。因此，除了这x个数字外，在其余数字种任意选取几个，它们的异或和也一定能够分解为这x个数字的线性组合，这是因为异或运算具有封闭性。然后在线性基下，可以选择的系数也只有0和1。也就意味着，N-x个数字种，选择任意一个子集，设它们的异或和为sum，那么我一定也能够在x个线性基的基底中找到一个子集，使得它们的异或和也为sum，这样两个集合的数字再异或起来，结果就是0，对应先手必败的方案。N-x个数字的自己个数是2^(N-x)，所以这就是先手必败的方案。那么最后的答案就是：
具体见代码：
#include<bits/stdc++.h>
#define mod 1000000007
#define LL long long
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define INF 0x3f3f3f3f
#define sf(x) scanf("%lld",&x)
#define sc(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
using namespace std;
struct Linear_Basis
{
LL b[14],tot;
void init(){memset(b,0,sizeof(b));tot=0;}
bool ins(LL x)
{
for(int i=13;i>=0;i--)
if (x&(1<<i))
{
if (!b[i]) {b[i]=x;tot++;break;}
x^=b[i];
}
return x>0;
}
} LB;
LL a,b,c,d,e,n,x,k;
char s[10000010];
bool v[4100];
LL qpow(LL x,LL n)
{
LL res=1;
n=(n+mod-1)%(mod-1);
while(n)
{
if (n&1) res=res*x%mod;
n>>=1; x=x*x%mod;
}
return res;
}
int main()
{
scanf("%s",s);
sc(x,a,b); sc(c,d,e);
LL m=0; sf(k);
for(int i=0;s[i];i++)
{
n=(n*10+s[i]-'0')%(mod-1);
if (n>k) m=INF;
}
LL ans=qpow(2,n);
LB.init(); if (m==0) m=n;
while(!v[x]&&m--)
{
v[x]=1; LB.ins(x);
x=(a*x*x*x*x+b*x*x*x+c*x*x+d*x+e-1LL)%k+1;
}
printf("%lld\n",(ans-qpow(2,(n-LB.tot)%(mod-1))+mod)%mod);
return 0;
}
全部评论 (0)
还没有任何评论哟~