NC54837. Nim游戏
描述
小F刚学习了博弈论，打算设计一个Nim游戏，去向同学炫耀一下。
小F有n个栈，第i栈中有ai个物品，其中的物品有bi种不同的排列方式。从 n 个栈里面选 k(>1) 个，其他的栈扔掉，任意决定这 k 个栈中物品的顺序，玩 Nim 游戏。
在游戏中，两人轮流操作。每人每次可以取走任意一个栈顶端的若干个物品。将所有物品取完的人赢。
因为小F要假装很大方地把先手让给同学，所以他希望设计出一个后手必胜的Nim游戏。请问总共有几种不同的设计方案。
输入描述
第一行包括一个正整数n。
接下来n行，每行两个正整数ai,bi。
输出描述
输出一个正整数。表示不同的方案数。答案对998244353取模。
示例1
输入:
3 1 1 2 2 3 3
输出:
6
C++(g++ 7.5.0) 解法, 执行用时: 324ms, 内存消耗: 1468K, 提交时间: 2022-11-17 23:43:11
#include<bits/stdc++.h>
using namespace std;
const int N=1<<17,mod=998244353,inv=998236737,M=1<<15;
int n,even[N],odd[N],ans;
char buf[M],*ie=buf+M,*ip=ie-1;
#define G ++ip==ie&&fread(ip=buf,1,M,stdin)
int read(){
int x=0;G;
while(!isdigit(*ip))G;
while(isdigit(*ip))x=x*10+*ip-48,G;
return x;
}
int main(){
n=read();
for(int i=0;i<N;i++)odd[i]=even[i]=1;
for(int i=1,x,y;i<=n;i++){
x=read();y=read();
even[x]=1ll*even[x]*(y+1)%mod;
odd[x]=1ll*odd[x]*(1-y)%mod;
}
for(int i=1;i<N;i<<=1)
for(int j=0;j<N;j+=i<<1)
for(int k=0;k<i;k++){
int a=even[j+k],b=odd[j+k],c=even[i+j+k],d=odd[i+j+k];
even[j+k]=1ll*a*c%mod;odd[j+k]=1ll*b*d%mod;
even[i+j+k]=1ll*a*d%mod;odd[i+j+k]=1ll*b*c%mod;
}
for(int i=0;i<N;i++)ans=(ans+even[i])%mod;
printf("%d\n",(1ll*ans*inv%mod-1+mod)%mod);
return 0;
}
C++ 解法, 执行用时: 1340ms, 内存消耗: 1456K, 提交时间: 2021-12-21 02:27:50
#include<bits/stdc++.h>
using namespace std;
const int N=1<<17,mod=998244353,inv=998236737,M=1<<15;
int n,even[N],odd[N],ans;
char buf[M],*ie=buf+M,*ip=ie-1;
#define G ++ip==ie&&fread(ip=buf,1,M,stdin)
template<typename T=int>T read(){T x;cin>>x;return x;}
int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
n=read();
for(int i=0;i<N;i++)odd[i]=even[i]=1;
for(int i=1,x,y;i<=n;i++){
x=read();y=read();
even[x]=1ll*even[x]*(y+1)%mod;
odd[x]=1ll*odd[x]*(1-y)%mod;
}
for(int i=1;i<N;i<<=1)
for(int j=0;j<N;j+=i<<1)
for(int k=0;k<i;k++){
int a=even[j+k],b=odd[j+k],c=even[i+j+k],d=odd[i+j+k];
even[j+k]=1ll*a*c%mod;odd[j+k]=1ll*b*d%mod;
even[i+j+k]=1ll*a*d%mod;odd[i+j+k]=1ll*b*c%mod;
}
for(int i=0;i<N;i++)ans=(ans+even[i])%mod;
printf("%d\n",(1ll*ans*inv%mod-1+mod)%mod);
return 0;
}