【CF1017D】The Wu（状压前缀和）

题意：给定n个a[i]，m个长为n的01串，定义串a与b之间的运算为a^b再按位取反，若第i位为1则运算结果加a[i]

q组询问(x,y)，每次询问m个串中与串x运算后答案小于等于y的串的个数

n<=12,q,m<=5e5,y<=1e2

思路：状压前缀和

预处理每个状态的权值

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<string>
  4 #include<cmath>
  5 #include<iostream>
  6 #include<algorithm>
  7 #include<map>
  8 #include<set>
  9 #include<queue>
 10 #include<vector>
 11 using namespace std;
 12 typedef long long ll;
 13 typedef unsigned int uint;
 14 typedef unsigned long long ull;
 15 typedef pair<int,int> PII;
 16 typedef vector<int> VI;
 17 #define fi first
 18 #define se second 
 19 #define MP make_pair
 20 #define N   1100000
 21 #define MOD 1000000007
 22 #define eps 1e-8 
 23 #define pi acos(-1)
 24 
 25 int f[4100],g[4100][110],a[N],b[N],c[N],flag[N];
 26 char ch[200],x[200];
 27 
 28 int read()
 29 { 
 30    int v=0,f=1;
 31    char c=getchar();
 32    while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
 33    while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
 34    return v*f;
 35 }
 36 
 37 void swap(int &x,int &y)
 38 {
 39     int t=x;x=y;y=t;
 40 }
 41 
 42 
 43 int main()
 44 {
 45 //    freopen("1.in","r",stdin);
 46     //freopen("1.out","w",stdout);
 47     int n,m,q;
 48     scanf("%d%d%d",&n,&m,&q);
 49     int max=(1<<n)-1; 
 50     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
 51     
 52     for(int i=1;i<=m;i++)
 53     {
 54         scanf("%s",ch);
 55         int now=1;
 56         int x=0;
 57         for(int j=n-1;j>=0;j--) 
 58         {
 59             if(ch[j]=='1') x+=now;
 60             now<<=1;
 61         }
 62         flag[x]++;
 63     }
 64        
 65        m=0;
 66     for(int i=0;i<=max;i++)
 67      if(flag[i]){b[++m]=i; c[m]=flag[i];}
 68   
 69   
 70 
 71     for(int i=0;i<=max;i++)
 72      for(int j=1;j<=n;j++)
 73       if(i&(1<<(j-1))) f[i]+=a[n-j+1];
 74 
 75     
 76     for(int i=0;i<=(1<<n);i++)
 77      for(int j=1;j<=m;j++) 
 78      {
 79          int t=f[(i^b[j])^max];
 80          if(t<=100) g[i][t]+=c[j];
 81      }
 82      
 83     for(int i=0;i<=(1<<n);i++)
 84      for(int j=1;j<=100;j++) g[i][j]+=g[i][j-1];
 85 
 86 
 87     for(int i=1;i<=q;i++)
 88     {
 89         int y;
 90         scanf("%s%d",x,&y);
 91         int now=1;
 92         int t=0;
 93         for(int j=n-1;j>=0;j--) 
 94         {
 95             if(x[j]=='1') t+=now;
 96             now<<=1;
 97         }
 98         y=min(y,100); 
 99         printf("%d
",g[t][y]);
100     }
101       
102     return 0;
103 }