---
title: Codeforce 1017 D. The Wu 解析(思維、二進位運算)
description: "Codeforce 1017 D. The Wu 解析(思維、二進位運算)"
disqus: hackmd
---
<meta name="robots" content="Codeforce 1017 D. The Wu 解析(思維、二進位運算)">
<!-- toc -->

# Codeforce 1017 D. The Wu 解析(思維、二進位運算)
今天我們來看看CF1017D
[題目連結](https://codeforces.com/problemset/problem/1017/D)

> **題目**
略，請直接看原題

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

<div class="VVVcopyrightAAA";>@copyright petjelinux 版權所有<br>
<a href="https://www.cnblogs.com/petjelinux/">觀看更多正版原始文章請至petjelinux的blog</a></div>

### 想法
只要注意到$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](https://codeforces.com/contest/1017/submission/91659696)