南京网络赛 The Great Nim Game
程序员文章站
2022-06-04 12:31:42
...
题意:
有n堆石子,从中选出k堆,使选出的石子进行nim游戏时先手必胜,求方案数。
题解:
nim游戏中,所有石子的异或和不为0,先手必胜,问题就化简为,n个数中的子集的异或和不为0的方案数。
dp[i][j]表示选前i个数,异或和为j的方案数。
dp方程:
dp[i][j]=dp[i-1][j^a[i]]*(选奇数个a[i]的方案数)+dp[i-1][j]*(选偶数个a[i]的方案数)
假设a[i]有x个,那么选奇数个a[i]的方案数和选偶数个a[i]的方案数都为2^(x-1)
方程化简为
设tot为数字的种类,设
Ans对100000007取模,根据费马小定理N-tot需对1000000006取模,再用快速幂即可。
代码:
#include<bits/stdc++.h>
#include<hash_map>
#define N 10000010
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi 3.141592653589793
#define LL long long
#define pb push_back
#define cl clear
#define si size
#define lb lowwer_bound
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define P 1000000007
#define mod 1000000007
using namespace std;
char s[N];
LL dp[2][4100],x,a,b,c,d,e,k;
LL qumi(LL x,LL y,LL mo)
{
LL res=1;
while(y)
{
if (y&1) res=res*x%mo;
x=x*x%mo;
y>>=1;
}
return res;
}
int fag[4100],f[4100];
int main()
{
while(~scanf("%s%lld",s,&x))
{
LL t=0;int tt=0;
for (int i=0;s[i];i++)
{
t=t*10+s[i]-'0';
t=t%(mod-1);
if (tt<4100) tt=tt*10+s[i]-'0';
}
scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&d,&e,&k);
mem(fag); f[1]=x; fag[x]=1; LL tot=tt;
for (int i=2;i<=tt;i++)
{
LL x=f[i-1];
f[i]=(a*x*x*x*x+b*x*x*x+c*x*x+d*x+e-1)%k+1;
if (fag[f[i]])
{
tot=i-1;
break;
}else fag[f[i]]=i;
}
t=(t-tot%(mod-1)+mod-1)%(mod-1);
int x=0,y=1;
mem(dp[0]); dp[0][0]=1;
for (int i=1;i<=tot;i++,swap(x,y))
for (int j=0;j<4096;j++) dp[y][j]=(dp[x][j^f[i]]+dp[x][j])%mod;
LL ans=0;
for (int i=1;i<4096;i++) ans=(ans+dp[x][i])%mod;
printf("%lld\n",ans*qumi(2,t,mod)%mod);
}
}
上一篇: 泡菜制作几部曲