正題

題目鏈接:https://www.luogu.com.cn/problem/CF838C

---

題目大意

一個字符串$s$，兩個人輪流操作，每次每個人可以選擇刪掉一個字符或者重排列這個字符串，但是不能出現(xiàn)之前出現(xiàn)過的字符串，不能操作者輸。

求有多少個長度為$n$且字符集大小為$k$的字符串使得先手必勝。

$1\le n\le 250000,1\le k\le 26$

---

解題思路

顯然如果刪掉一個字符能使得先手必敗，那么先手必勝。如果不能，那么肯定會一直重排列這個字符串。

那么如果一個字符串的排列數(shù)是偶數(shù)，那么先手可以切換先后手，所以先手必勝。否則先手需要考慮能否刪除一個字符使得先手必敗。

設第$i$個字符的數(shù)量是$a_i$，那么一個字符串可重排列的方案就是$\frac{n!}{{\prod }_{i=1}^k{a}_i!}$，并且如果刪除一個字符$i$，那么排列方式將會乘上$\frac{a_i}{n}$。

那么如果$n$是奇數(shù)，肯定存在一個$a_i$是奇數(shù)，也就是說刪除一個$i$后排列方式的奇偶性不變。所以如果一個$n$是奇數(shù)且字符串的排列數(shù)是奇數(shù)，那么肯定可以刪除一個字符使得排列數(shù)仍然是偶數(shù)。
那么如果$n$是奇數(shù)且先手，那么肯定不會被逼到一個走動后先手必勝的位置，所以$n$是奇數(shù)先手必勝。

然后如果$n$是偶數(shù)，那么如果排列方式是偶數(shù)那么先手必勝否則先手必敗。

然后考慮怎么計數(shù)$n$是偶數(shù)的情況。考慮到一個$n!$包含的$2$質(zhì)因數(shù)的個數(shù)為${\sum }_{i=0}?\frac{n}{2^i}?$，那么如果一個字符串的排列方式是偶數(shù)那么肯定有
$$\sum _{i=0}?\frac{n}{2^i}?=\sum _{p=1}^k\sum _{i=0}?\frac{a_p}{2^i}?$$
然后又因為假設我們考慮一直分解$x$出來，顯然${\prod }_{i=1}^k{a}_i!$的$x$肯定不會比$n!$中$x$多，同理分解$2^k$出來也是一樣的，所以它們每一個$i$求出來的答案都是恰好相等的，即
$$?i\in N,?\frac{n}{2^i}?=\sum _{p=1}^k?\frac{a_p}{2^i}?$$
那么$a_i$求和的時候二進制就不能有進位了，也就是說對于$n$中的每個$1$，$a_i$都恰好有一個是$1$，$n$中的每一個$0$，$a_i$這一位都是$0$。

也就是把$n$的二進制分成若干份$a_i$，每一份的貢獻是$\frac{1}{a_i!}$，要求貢獻的乘積和。這個分出一個部分來的轉(zhuǎn)移其實就是子集卷積，所以我們跑$k$次子集卷積即可。

這樣跑有點慢，所以我們還需要快速冪優(yōu)化。

時間復雜度：$O(k\log kn{\log }^{2}n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define lowbit(x) (x&-x) using namespace std; const int N=1<<19; int n,k,P,f[20][N],g[20][N],c[N],inv[N],fac[N]; void FWT(int *f,int n,int op){for(int p=2;p<=n;p<<=1)for(int k=0,len=p>>1;k<n;k+=p)for(int i=k;i<k+len;i++)(f[i+len]+=f[i]*op)%=P;return; } signed main() {scanf("%d%d%d",&n,&k,&P);int ans=1;for(int i=1;i<=n;i++)ans=1ll*ans*k%P;fac[0]=inv[0]=inv[1]=1;for(int i=2;i<N;i++)inv[i]=P-1ll*inv[P%i]*(P/i)%P;for(int i=1;i<N;i++)fac[i]=1ll*fac[i-1]*i%P,inv[i]=1ll*inv[i-1]*inv[i]%P;if(n&1)return printf("%d\n",ans)&0;f[0][0]=1;int m=1,lg=0;while(m<=n)m<<=1,lg++;for(int i=1;i<m;i++)c[i]=c[i-lowbit(i)]+1;for(int i=0;i<=n;i++)g[c[i]][i]=inv[i];for(int i=0;i<c[n];i++)FWT(g[i],m,1);FWT(f[0],m,1);while(k){if(k&1){for(int i=c[n];i>=0;i--){for(int x=0;x<m;x++)f[i][x]=1ll*f[i][x]*g[0][x]%P;for(int j=1;j<=i;j++)for(int x=0;x<m;x++)f[i][x]=(f[i][x]+1ll*f[i-j][x]*g[j][x])%P;}}for(int i=c[n];i>=0;i--){for(int x=0;x<m;x++)g[i][x]=(i?2ll:1ll)*g[0][x]*g[i][x]%P;for(int j=1;j<i;j++)for(int x=0;x<m;x++)g[i][x]=(g[i][x]+1ll*g[j][x]*g[i-j][x])%P;}k>>=1;}FWT(f[c[n]],m,-1);ans=(ans-1ll*f[c[n]][n]*fac[n]%P)%P;printf("%d\n",(ans+P)%P);return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF838C-Future Failure【dp,子集卷积】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。