欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

南京网络赛 The Great Nim Game

程序员文章站 2022-06-04 12:31:42
...

南京网络赛 The Great Nim Game

南京网络赛 The Great Nim Game

南京网络赛 The Great Nim Game

南京网络赛 The Great Nim Game

 

题意:

有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)

方程化简为

南京网络赛 The Great Nim Game

设tot为数字的种类,设 南京网络赛 The Great Nim Game

南京网络赛 The Great Nim Game

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);
	}
}

 

相关标签: 南京网络赛