題目鏈接：點(diǎn)擊查看

題目大意：規(guī)定一張?jiān)嚲砩嫌?$m$ 個(gè)問(wèn)題，每個(gè)問(wèn)題只有 $A,B$ 兩個(gè)選項(xiàng)，現(xiàn)在給出 $n$ 張?jiān)嚲怼Ｐ枰x擇一個(gè)問(wèn)題的子集，使得有大于等于 $k$ 對(duì)試卷的答案是不完全相同的，問(wèn)這樣的子集有多少個(gè)

題目分析：若將選項(xiàng)轉(zhuǎn)換為 $0$ 或 $1$，試卷視為 $01$ 串，那么兩個(gè)試卷相同，當(dāng)且僅當(dāng)異或和等于 $0$。

設(shè) $a_i$ 為第 $i$ 個(gè)試卷所代表的 $01$ 串， $F(S)$ 為異或和等于 $S$ 的 $01$ 串對(duì)的個(gè)數(shù)，則

$$F(S)=\sum _{i=1}^n\sum _{j=i}^n[a_i\oplus a_j=S]$$

不難發(fā)現(xiàn)可以轉(zhuǎn)換為卷積的形式，設(shè) $num[x]$ 為 $x$ 的出現(xiàn)次數(shù)，則

$$F(S)=\frac{1}{2}\sum _{i\oplus j=S}num[i]?num[j]$$

設(shè) $G(T)$ 為問(wèn)題集合為 $T$ 時(shí)，有多少對(duì)試卷是不相同的，則

$$G(T)=\sum _{T\cap S=?}F(S)$$

容斥一下

$$G(T)=\frac{n^2}{2}?\sum _{T\cap S=?}F(S)=\frac{n^2}{2}?\sum _{S?(U?T)}F(S)$$

可能有些同學(xué)會(huì)有疑問(wèn)，為什么這里突然出來(lái)一個(gè) $\frac{n^2}{2}$，因?yàn)楦鶕?jù) $F(S)$ 的定義，$F(S)$ 的最大值是這個(gè)數(shù)，所以設(shè)置為 $F$ 函數(shù)的“全集”。

然后 $U$ 是全集，$U?T$ 自然也就是 $T$ 的補(bǔ)集。

到此公式就推完了，$F(S)$ 可以用 $FWT$ 快速求解，$G(T)$ 可以用 $SOSdp$ 快速求解

代碼：

// Problem: United in Stormwind // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/18713/M // Memory Limit: 2097152 MB // Time Limit: 4000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=5e6+100; char s[N]; double F[N]; LL G[N]; void FWTxor(double *f,double x,int len) {for(int mid=1;(mid<<1)<=len;mid<<=1){int R=mid<<1;for(int i=0;i<len;i+=R)for(int j=0;j<mid;j++){f[i+j]=f[i+j]+f[i+j+mid];f[i+j+mid]=f[i+j]-f[i+j+mid]-f[i+j+mid];f[i+j]=f[i+j]*x;f[i+j+mid]=f[i+j+mid]*x;}} } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;LL k;read(n),read(m),read(k);for(int i=1;i<=n;i++) {scanf("%s",s);int state=0;for(int j=0;j<m;j++) {if(s[j]=='A') {state|=(1<<j);}}F[state]+=1.0;}FWTxor(F,1,1<<m);for(int i=0;i<1<<m;i++) {F[i]*=F[i];}FWTxor(F,0.5,1<<m);for(int i=0;i<1<<m;i++) {G[i]=LL(F[i]/2);}for(int j=0;j<m;j++) {for(int i=0;i<1<<m;i++) {if(i>>j&1) {G[i]+=G[i^(1<<j)];}}}int ans=0;for(int i=0;i<1<<m;i++) {if(1LL*n*n-G[i]*2>=k*2) {ans++;}}cout<<ans<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的2020ICPC沈阳 - United in Stormwind(推公式+FWT+SOSdp)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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