题目
(S)串长为(n)，字符集大小为(k)
一次操作为：取走(S)的任意一个字符或将(S)重排为一个没有出现过的字符(S')
询问有多少个(S)使得后手必胜，答案对(P)取模
$n le 3 imes 10^5 , k le 10^9 , 10^8 le P le 10^9+100 $
题解
-
part 1 博弈
先手必败当且仅当(n)为偶数，且不同的重排字符个数为奇数(难怪所有sample没有一个n为奇数)
设每一个字符出现的次数为(a_i)，不同的个数为((^{ n }_{a_1 a_2 cdots a_k}))
对n=1显然成立
如果(n)为偶数，(n-1)为奇数
这时删掉这个字符的人一定是必拜的
如果不同个数为偶数，删掉一个字符的一定是后手，否则一定是先手
如果(n)为奇数，刪去一个字符(i)相当于将方案乘以(frac{a_i}{n})
考虑重排数为奇数，一定存在一个$a_i $为奇数，先手操作这个数必胜
考虑重排数为偶数，由于(n)为奇数，到时n-1的个数一定仍然为偶数
这时删掉字符的人输，而删掉字符的人一定是后手
所以结论成立
-
part 2 计数部分
问题变成求$(^{ n }_{a_1 a_2 cdots a_k}) % 2 = 1 , sum a_i =n $的个数
((^n_{a_1 , cdots , a_k})) %P 不为0当且仅当拆分成P进制之后(a1 & cdots & a_k = 0)
考虑集合幂级数(F(x) = sum frac{1}{i!}) ，相当于求(F(x))子集卷积的(k)次幂
这可以用全家桶的exp和ln优化
-
part 3 ln和exp
如果直接用(nlog n)的exp和ln，乘法长度会从18变成32，常数巨大
所以需要用(n^2)的多项式exp和ln（pty讲述了一下推法）
考虑f和exp(f)的关系等价于无向连通图的EGF和无向图的EGF之间的关系
考虑暴力地递推：
[egin{align} &考虑G(x)为连通图个数的EGF，F(x)为无向图个数的EGF:\ &考虑无向连通图和无向图之间的递推\ &egin{cases} F_i = frac{f_i}{i!} , G_i = frac{g_i}{i!}\ F = exp(G) \ f_i = sum_{j=1}^{i} (^i_{j-1}) g_i f_{i-j} \ end{cases} 化简得：\ &egin{cases} G_0 = 0 , F_0 = 1\ F_i = frac{1}{i}sum_{j=1}^{i} jG_jF_{i-j}\ G_i = F_i - frac{1}{i}sum_{j=1}^{i-1}jG_jF_{i-j}\ end{cases} end{align} ]这样就可以做到(n^2)
时间复杂度(O(n log ^2 n ))
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define rg register
using namespace std;
const int N=1<<19,M=20;
int n,m,mx,P,L,a[M][N],cnt[N],b[N],c[N],ny[N],fac[N],inv[N];ll lim;
il void inc(int&x,int y){x+=y;if(x>=P)x-=P;}
il void dec(int&x,int y){x-=y;if(x<0)x+=P;}
il void fwt(int*A){
for(rg int i=1;i<L;i<<=1)
for(rg int j=0;j<L;j+=i<<1)
for(rg int k=0;k<i;++k){
inc(A[j+k+i],A[j+k]);
}
}
il void ifwt(int*A){
for(rg int i=1;i<L;i<<=1)
for(rg int j=0;j<L;j+=i<<1)
for(rg int k=0;k<i;++k){
dec(A[j+k+i],A[j+k]);
}
}
il void exp(int*A,int*B,int l){
B[0]=1;
for(rg int i=1;i<=l;++i){
B[i]=0;ll t=0;
for(rg int j=1;j<=i;++j){
//inc(B[i],1ll*j*A[j]%P*B[i-j]%P);
t+=1ll*A[j]*B[i-j]%lim*j;
if(t>=lim)t-=lim;
}
//B[i]=1ll*B[i]*ny[i]%P;
B[i]=(t%P)*ny[i]%P;
}
}
il void ln(int*A,int*B,int l){
B[0]=0;
for(int i=1;i<=l;++i){
B[i]=0;ll t=0;
for(rg int j=1;j<i;++j){
//dec(B[i],1ll*j*B[j]%P*A[i-j]%P);
t+=1ll*B[j]*A[i-j]%lim*j;
if(t>=lim)t-=lim;
}
//B[i]=(A[i]+1ll*B[i]*ny[i])%P;
B[i]=(A[i]+(P-t%P)*ny[i])%P;
}
}
il void pow(int*A,int k,int l){
static int t1[N];
ln(A,t1,l);
for(int i=0;i<=l;++i)t1[i]=1ll*t1[i]*k%P;
exp(t1,A,l);
}
int main(){
freopen("megalovania.in","r",stdin);
freopen("megalovania.out","w",stdout);
scanf("%d%d%d",&n,&m,&P);
if(n&1)return puts("0"),0;
lim=(ll)4e18/P*P;
L=1;while(L<=n)L<<=1;
ny[1]=1;for(int i=2;i<=n;++i)ny[i]=1ll*(P-P/i)*ny[P%i]%P;
for(int i=fac[0]=inv[0]=1;i<=n;++i){
fac[i]=1ll*fac[i-1]*i%P;
inv[i]=1ll*inv[i-1]*ny[i]%P;
cnt[i]=cnt[i>>1]+(i&1);
}
mx=cnt[n];
for(int i=0;i<=n;++i)if((i|n)==n)a[cnt[i]][i]=inv[i];
for(int i=0;i<=mx;++i)fwt(a[i]);
for(int i=0;i<=n;++i)if((i|n)==n){
for(int j=0;j<=mx;++j)b[j]=a[j][i];
pow(b,m,mx);
c[i]=b[mx];
}
ifwt(c);
int ans=1ll*c[n]*fac[n]%P;
cout<<ans<<endl;
return 0;
}