document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. #include<cstdio>
  2. const int SIZE = 1<<20;
  3. long long dp[SIZE];
  4. int a[SIZE];
  5. int main(){
  6.     int n,q;
  7.     scanf("%d%d",&n,&q);
  8.     for(int i=0;i<n;i++){
  9.         char s[24];
  10.         scanf("%s",s);
  11.         for(int j=0;j<20;j++)a[i]|=(int)(s[j]-\'0\')<<j;
  12.         dp[a[i]]++;
  13.     }
  14.     // calculate the number of S_i belong to T
  15.     for(int i=0;i<20;i++)
  16.         for(int j=SIZE-1;j>=0;j--)
  17.             if((j>>i)&1)dp[j]+=dp[j^(1<<i)];
  18.     // calculate the number of (i,j) satisfying i<j and (S_i U S_j) belong to T
  19.     for(int i=0;i<SIZE;i++)
  20.         dp[i]=dp[i]*(dp[i]-1)/2;
  21.     // calculate the number of (i,j) satisfying i<j and (S_i U S_j) = T
  22.     for(int i=19;i>=0;i--)
  23.         for(int j=0;j<SIZE;j++)
  24.             if((j>>i)&1)dp[j]-=dp[j^(1<<i)];
  25.     // calculate the number of (i,j) satisfying i<j and T belong to (S_i U S_j)
  26.     for(int i=0;i<20;i++)
  27.         for(int j=0;j<SIZE;j++)
  28.             if((j>>i)&1)dp[j^(1<<i)]+=dp[j];
  29.     while(q--){
  30.         long long an=0;
  31.         int x=0;
  32.         char s[24];
  33.         scanf("%s",s);
  34.         for(int j=0;j<20;j++)x|=(int)(s[j]-\'0\')<<j;
  35.         printf("%I64d\\n",dp[x]);
  36.     }
  37. }
');