gym102798 2020CCPC威海J Steins；Game

题目：

给定$n$堆石子$a$，每堆石子被染成了黑色或者白色，现在两个人轮流进行以下的其中一个操作：
1、从石子数量最少的一个黑色石堆中拿走若干石子
2、从任意一个白色石堆中拿走若干石子
两个人都采取最优策略，不能操作者输。现在染色工作由后手的人完成，问有多少种染色方案可以使后手赢。
$(1\le n\le 10^5,1\le a_i\le 10^{18})$

题解：

首先黑色和白色的石堆不相干，可以看成两个游戏的和，白色石堆就是在玩$Nim$，$SG$函数就是白色石堆石子数的异或和。黑色石堆的$SG$函数通过打表（下附打表程序）找规律得到，为$min-(num+[所有黑色石堆的石子数量一样])\%2$，其中$min$为黑色石堆中数量最少的石堆的石子数，$num$为石子数量最少的黑色石堆的堆数。那么最终游戏的$SG$就是两种$SG$异或起来。我们可以发现黑色石堆的$SG$基本上只和石子数量最少的黑色石堆有关，和其他的黑色石堆无关，所以考虑将石堆$a$按数量从小到大排序，然后从小到大枚举最小的黑色石堆的石子数$a_i$和石堆数$k$，那么比这更小的石堆都染成了白色，所以需要考虑的就是$[i+k,n]$的石堆的染色情况。我们要使最终的$SG$为0，根据黑色石堆的$SG$式子，待定石堆分为两种情况：
1、全染成白色
2、有一部分染成黑色
从而可以得到对应情况的黑色石堆的$SG$，设为$black$，维护出石堆$a$的前缀异或和$pre$和后缀异或和$suf$，那么现在知道了前面部分的$SG$为$part=pr{e}_{i-1}\oplus black\oplus [(num-k)\%2=0]a_i$，其中$num$为$n$堆石子中石子数为$a_i$的石堆的数量，如果我们可以算出待定石堆的染色方案数$x$，那么这部分枚举对答案的贡献为$x\left(\genfrac{}{}{0ex}{}{num}{k}\right)$。考虑怎么算$x$，对于第一种情况，直接判断$su{f}_{i+k}$是否等于$part$即可；对于第二种情况，如果$[i+num,n]$的石堆无法异或出$part$，那么就对答案没有贡献，不然就有贡献，考虑用线性基来做，对于每个后缀$i$我们维护出一个线性基$L{B}_i$，根据线性基的性质可知$L{B}_i$中的数可以唯一的表出$\text{span}(a_{i...n})$，所以对于第一种情况直接判线性基中的数是否能表出$part$即可。如果可以表出，考虑计数，由于线性基表出的唯一性，所以对于不在线性基中的数的所有子集，在线性基中都可以唯一找出一些数和它的异或和为0，然后再异或上线性基中唯一可以异或出$part$的那些数，最后就可以异或出$part$，所以所有不在线性基中的数的所有子集都会算一次贡献，那么在本题中，如果$L{B}_{i+num}$的大小为$r$，那么贡献为$2^{n-(i+num)+1-r}$，需要注意的是如果$[i+num,n]$全染白的方案是可行的，那么就要减去这个方案的贡献，因为和前提冲突。

复杂度： O ( n l o g ( max ⁡ { a i } ) ) O(nlog(max{a_i})) O(nlog(max{ai​}))

代码：

打表程序

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<bitset>
#include<sstream>
#include<ctime>
//#include<chrono>
//#include<random>
//#include<unordered_map>
using namespace std;

#define ll long long
#define ls o<<1
#define rs o<<1|1
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
const double pi=acos(-1.0);
const double eps=1e-6;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const int maxn=15;
ll read(){
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int sg[maxn][maxn][maxn][maxn][maxn],vis[maxn];
int dfs(int len,int a,int b,int c,int d,int e){
	if(sg[a][b][c][d][e]!=-1)return sg[a][b][c][d][e];
	if(len==0){
		sg[0][0][0][0][0]=0;
		return 0;
	}
	if(len==1){
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=e;i++){
			vis[dfs(len-(i==e?1:0),a,b,c,d,e-i)]=1;
		}
		for(int i=0;;i++){
			if(!vis[i]){
				sg[a][b][c][d][e]=i;
				break;
			}
		}
	}	
	else if(len==2){
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=d;i++){
			vis[dfs(len-(i==d?1:0),a,b,c,d-i,e)]=1;
		}
		for(int i=0;;i++){
			if(!vis[i]){
				sg[a][b][c][d][e]=i;
				break;
			}
		}
	}
	else if(len==3){
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=c;i++){
			vis[dfs(len-(i==c?1:0),a,b,c-i,d,e)]=1;
		}
		for(int i=0;;i++){
			if(!vis[i]){
				sg[a][b][c][d][e]=i;
				break;
			}
		}
	}
	else if(len==4){
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=b;i++){
			vis[dfs(len-(i==b?1:0),a,b-i,c,d,e)]=1;
		}
		for(int i=0;;i++){
			if(!vis[i]){
				sg[a][b][c][d][e]=i;
				break;
			}
		}
	}
	else{
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=a;i++){
			vis[dfs(len-(i==a?1:0),a-i,b,c,d,e)]=1;
		}
		for(int i=0;;i++){
			if(!vis[i]){
				sg[a][b][c][d][e]=i;
				break;
			}
		}
	}
	return sg[a][b][c][d][e];
}
void sg_table(){
	memset(sg,-1,sizeof(sg));
	for(int i=0;i<=10;i++){
		for(int j=i;j<=10;j++){
			for(int k=j;k<=10;k++){
				for(int h=k;h<=10;h++){
					for(int it=h;it<=10;it++){
						int len=0;
						if(i!=0){
							len=5;
						}
						else if(j!=0){
							len=4;
						}
						else if(k!=0){
							len=3;
						}
						else if(h!=0){
							len=2;
						}
						else if(it!=0){
							len=1;
						}
						else len=0;
						dfs(len,i,j,k,h,it);
						int a=i;
						int b=j;
						int c=k;
						int d=h;
						int e=it;
						int num=0,min,max=it;
						if(len==0){
							min=0;
							num=0;
						}
						if(len==1){
							min=e;
							num=1;
						}
						else if(len==2){
							min=d;
							num=1;
							if(e==d)num++;
						}
						else if(len==3){
							min=c;
							num=1;
							if(d==c){
								num++;
							}
							if(e==c)num++;
						}
						else if(len==4){
							min=b;
							num=1;
							if(c==b)num++;
							if(d==b)num++;
							if(e==b)num++;
						}
						else if(len==5){
							min=a;
							num=1;
							if(b==a)num++;
							if(c==a)num++;
							if(d==a)num++;
							if(e==a)num++;
						}
						// int tmp=min-(num+(max==min))%2;
						// if(sg[a][b][c][d][e]!=tmp){
						// 	printf("%d %d %d %d %d %d %d %dn",len,a,b,c,d,e,sg[a][b][c][d][e],tmp);
						// }
						printf("%d %d %d %d %d %d %dn",len,i,j,k,h,it,dfs(len,i,j,k,h,it));
					}
				}
			}
		}
	}
}
int main(void){
	//freopen("in.txt","r",stdin);
	// freopen("sg.out","w",stdout);
	sg_table();
	return 0;
}

AC程序

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<bitset>
#include<sstream>
#include<ctime>
//#include<chrono>
//#include<random>
//#include<unordered_map>
using namespace std;

#define ll long long
#define ls o<<1
#define rs o<<1|1
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
const double pi=acos(-1.0);
const double eps=1e-6;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const int maxn=1e5+5;
ll read(){
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n;
ll a[maxn],suf[maxn],fac[maxn],ifac[maxn];
struct Linear_Basis{
	ll a[62];
	int lim=60,r=0;
	//插入线性基
	void init(){
		r=0;
		for(int i=0;i<=lim;i++)a[i]=0;
	}
	//插入
	bool ins(ll x){
		for(int i=lim;i>=0&&x;i--){
			if(x&(1LL<<i)){
				if(a[i]){
					x^=a[i];
				}
				else{
					a[i]=x;
					++r;
					break;
				}
			}
		}
		if(x)return true;
		else return false;
	}
	// 判断x能否由线性基中的数线性表出
	bool qryExist(ll x){
		for(int i=lim;i>=0&&x;i--){
			if(x&(1LL<<i)){
				if(a[i]){
					x^=a[i];
				}
				else{
					return false;
				}
			}
		}
		return true;
	}
	//得到x与线性基中数的最大异或和,当x=0时，得到线性基中数的最大异或和
	ll qryMax(ll x){
		for(int i=lim;i>=0;i--){
			if((x^a[i])>x)x^=a[i];
		}
		return x;
	}
}LB[maxn];
ll qpow(ll a,ll p=mod-2){
	ll res=1;
	while(p){
		if(p&1)res=res*a%mod;
		a=a*a%mod;
		p>>=1;
	}
	return res;
}
void init(int n){
	fac[0]=1;
	for(int i=1;i<=n;i++){
		fac[i]=fac[i-1]*i%mod;
	}
	ifac[n]=qpow(fac[n]);
	for(int i=n-1;i>=0;i--){
		ifac[i]=ifac[i+1]*(i+1)%mod;
	}
}
ll C(int n,int m){
	return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main(void){
	// freopen("in.txt","r",stdin);
	scanf("%d",&n);
	init(n);
	ll flag=0;
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		flag^=a[i];
	}
	sort(a+1,a+n+1);
	suf[n+1]=0;
	LB[n+1].init();
	for(int i=n;i>=1;i--){
		memcpy(LB[i].a,LB[i+1].a,sizeof(LB[i+1].a));
		LB[i].r=LB[i+1].r;
		LB[i].ins(a[i]);
		suf[i]=suf[i+1]^a[i];
	}
	ll pre=0,ans=0;
	for(int i=1,j;i<=n;i=j){
		for(j=i;j<=n;j++){
			if(a[j]==a[i])continue;
			break;
		}
		int num=j-i;
		for(int k=1;k<=num;k++){
			//min!=max
			if(j<=n){
				ll black=a[i]-k%2;
				ll tar=pre^black^((num-k)%2?a[i]:0);
				if(LB[j].qryExist(tar)){
					ans=(ans+qpow(2,n-j+1-LB[j].r)*C(num,k)%mod)%mod;
					if(suf[j]==tar)ans=(ans-C(num,k))%mod;
				}
			}
			
			//min=max
			ll black=a[i]-(k+1)%2;
			ll tar=pre^black^((num-k)%2?a[i]:0);
			if(suf[j]==tar)ans=(ans+C(num,k))%mod;
		}
		if(num%2)pre^=a[i];
	}
	ans=(ans+(flag==0))%mod;
	printf("%lldn",(ans%mod+mod)%mod);
	return 0;
}

最后

以上就是彪壮火车为你收集整理的gym102798 2020CCPC威海J Steins；Game的全部内容，希望文章能够帮你解决gym102798 2020CCPC威海J Steins；Game所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。