Codeforce 1017 D. The Wu 解析(思維、二進位運算)

今天我們來看看CF1017D
題目連結

題目
略，請直接看原題

前言

官方解答實在看不懂…之後還記得的話再補那個做法吧

想法

只要注意到$n\le12$代表所有可能出現的數字$\le\sum\limits_{i=0}^{11}2^i=2^{12}-1=4096-1$，那就會注意到這題的$m,q\le5\cdot10^5$是假的，因為總共也才$4096$種字串，哪來的$5\cdot10^5$這麼多數字讓你問?
所以這題只需要把所有的詢問字串都窮舉一遍，並且直接計算「當前詢問字串與$m$個$multiset$裡的字串計算Wu值，每個值有多少個」儲存起來(只需要儲存Wu值$\le100$，因為$k\le100$)，那麼之後每次詢問只需要$O(100)$就可以找到答案了(計算前綴和)。

實作細節:首先把$multiset$裡的元素都看成數字；$cnt[i]=multiset$中$i$的個數；$(s,t)$的Wu值只和$s,t$哪些$bit$相同有關，$wu[(s,t)兩個數字bit相同的位置標為1其他為0的數字]=Wu(s,t)$
而要計算(s,t)兩個數字bit相同的位置標為1其他為0的數字只需要:$(s\widehat{}(\sim t))&((1<<n)-1)=(s\widehat{}(\sim t))&\sim-(1<<n)$，其中$(1<<n)-1是用來只保留小於1<<n的bit$，而$(1<<n)-1=\sim-(1<<n)$是利用$-k=\sim k+1$

程式碼:

const int _n=15;  
int t,n,m,q,w[_n],k,cnt[4096],ans[4096][110],wu[4096];  
char s[_n];  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>n>>m>>q;rep(i,1,n+1)cin>>w[i];  
  rep(i,0,1<<n)rep(j,0,n)wu[i]+=w[n-j]*((i&(1<<j))>0);  
  rep(i,0,m){  
    int num=0;cin>>(s+1);  
    rep(j,0,n)num+=(s[n-j]-'0')*(1<<j);  
    cnt[num]++;  
  }rep(qu,0,1<<n)rep(ts,0,1<<n){  
    ans[qu][wu[(qu^~ts)&~-(1<<n)]>100?101:wu[(qu^~ts)&~-(1<<n)]]+=cnt[ts];  
  }while(q--){  
    cin>>(s+1)>>k;  
    t=0;rep(j,0,n)t+=(s[n-j]-'0')*(1<<j);  
    int res=0;rep(i,0,k+1)res+=ans[t][i];  
    cout<<res<<'\n';  
  }  
  return 0;  
}  

標頭、模板請點Submission看
Submission