題目鏈接

https://loj.ac/problem/6358

題意

題面寫得就像一坨X一樣，我來復(fù)述一下吧。
有\(n\)個元素構(gòu)成的集合，要從\(2^n\)個子集中選出若干個使得交的大小為\(4\)的倍數(shù)。不選算交為空。
樣例解釋: 選空集有\(8\)種方案，不選空集方案只有\(\{ 1\} \{ 2\}\)和\(\{ 1\} \{ 2\} \{1,2\}\), 還有一種什么都不選，共\(11\)種。

題解

這道題真的神仙得令我目瞪口呆。。

首先考慮一個簡單的容斥: 令\(F(k)\)表示欽定\(k\)個元素在所有選出的子集中必須出現(xiàn)，則\(F(k)={n\choose k}(2^{2^{n-k}}-1)\).
令\(G(k)\)表示交集恰好為\(k\)的方案數(shù)，則有\(F(k)=\sum^{n}_{i=k} {k\choose i}G(k), G(k)=\sum^{n}_{i=k} (-1)^{i-k}{k\choose i}F(k)\).
那么要求的就是\(ans=\sum^n_{k\equiv 0(\mod 4)} G(k)\).

前方高能——
我們考慮構(gòu)造一個系數(shù)\(\alpha(i)\) (官方題解將它稱為“容斥系數(shù)” ) 使得\(ans=\sum^{n}_{i=0}F(i)\alpha(i)\).
如果沒有\(k\)是\(4\)的倍數(shù)這個條件，對所有\(k\)求和，那么根據(jù)容斥的式子可以推出來\(\alpha(i)=[i=0]\)即可達到目的。
現(xiàn)在有了這個條件，我們考慮剛才實際上我們在干什么:
對于一個\(G(n)\), 其在\(F(k)\)中會被計算\(n\choose k\)次，我們希望總共計算的次數(shù)是\(1\)次，那么也就是\[\forall n, \sum^{n}_{k=0} {n\choose k}\alpha(k)=1\], 取\(\alpha(k)=[k=0]\)即可. 現(xiàn)在我們就是要\(\forall n, \sum^{n}_{k=0} {n\choose k}\alpha(k)=[k\equiv 0(\mod 4)]\). 于是根據(jù)二項式反演有\(F(n)=\sum^{n}_{k=0} (-1)^{n-k}{n\choose k}[k\equiv 0(\mod 4)]\).

這個東西怎么快速求？掏出數(shù)論中走街串巷殺題越貨之必備良品——單位根！令\(m=4\), \(\omega\)為\(4\)次(主)單位根，則有\[[n\equiv 0(\mod m)]=\frac{1}{n}\sum^{m-1}_{i=0} \omega^{in}\]
于是\(\alpha(n)=\frac{1}{m}\sum^{n}_{k=0}(-1)^{n-k}{n\choose k}\sum^{m-1}_{i=0}(\omega^i)k=\sum^{m-1}_{i=0}(\omega^i-1)^k\)
直接計算即可。

時間復(fù)雜度\(O(nm)\).

啟示: 最近連做了兩道神仙構(gòu)造的題，經(jīng)常可以構(gòu)造一些轉(zhuǎn)移矩陣/容斥系數(shù)/遞推式之類的東西以達到目的，這種思路值得借鑒。

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<cassert> #include<iostream> #define llong long long using namespace std;inline int read() {int x=0; bool f=1; char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=0;for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');if(f) return x;return -x; }const int N = 1e7; const int P = 998244353; const llong G = 3ll; const llong W = 911660635ll; const llong INV4 = 748683265ll;int fact[N+3],finv[N+3]; llong f[N+3],a[N+3]; int n;llong quickpow(llong x,llong y) {llong cur = x,ret = 1ll;for(int i=0; y; i++){if(y&(1ll<<i)) {y-=(1ll<<i); ret = ret*cur%P;}cur = cur*cur%P;}return ret; } llong comb(llong x,llong y) {return x<0||y<0||x<y ? 0ll : (llong)fact[x]*(llong)finv[y]%P*(llong)finv[x-y]%P;}int main() {fact[0] = 1ll; for(int i=1; i<=N; i++) fact[i] = (llong)fact[i-1]*i%P;finv[N] = quickpow(fact[N],P-2); for(int i=N-1; i>=0; i--) finv[i] = (llong)finv[i+1]*(i+1ll)%P;scanf("%d",&n);f[n] = 2ll; for(int i=n-1; i>=0; i--) f[i] = f[i+1]*f[i+1]%P;for(int i=0; i<=n; i++) f[i]--;for(int i=0; i<=n; i++) f[i] = f[i]*comb(n,i)%P;for(int i=0; i<4; i++){llong tmp = 1ll,expn = quickpow(W,i);for(int j=0; j<=n; j++){a[j] = (a[j]+tmp)%P;tmp = tmp*(expn-1ll)%P;}}for(int i=0; i<=n; i++) a[i] = a[i]*INV4%P; // for(int i=0; i<=n; i++) printf("%lld ",a[i]); puts("");llong ans = 1ll;for(int i=0; i<=n; i++) ans = (ans+f[i]*a[i])%P;printf("%lld\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的LOJ #6358 前夕 (组合计数、容斥原理)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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