week16- B3. Two Swords Style Hard, Author Solution

#include<cstdio>
const int SIZE = 1<<20;
long long dp[SIZE];
int a[SIZE];
int main(){
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=0;i<n;i++){
        char s[24];
        scanf("%s",s);
        for(int j=0;j<20;j++)a[i]|=(int)(s[j]-'0')<<j;
        dp[a[i]]++;
    }
    // calculate the number of S_i belong to T
    for(int i=0;i<20;i++)
        for(int j=SIZE-1;j>=0;j--)
            if((j>>i)&1)dp[j]+=dp[j^(1<<i)];
    // calculate the number of (i,j) satisfying i<j and (S_i U S_j) belong to T
    for(int i=0;i<SIZE;i++)
        dp[i]=dp[i]*(dp[i]-1)/2;
    // calculate the number of (i,j) satisfying i<j and (S_i U S_j) = T
    for(int i=19;i>=0;i--)
        for(int j=0;j<SIZE;j++)
            if((j>>i)&1)dp[j]-=dp[j^(1<<i)];
    // calculate the number of (i,j) satisfying i<j and T belong to (S_i U S_j)
    for(int i=0;i<20;i++)
        for(int j=0;j<SIZE;j++)
            if((j>>i)&1)dp[j^(1<<i)]+=dp[j];
    while(q--){
        long long an=0;
        int x=0;
        char s[24];
        scanf("%s",s);
        for(int j=0;j<20;j++)x|=(int)(s[j]-'0')<<j;
        printf("%I64d\n",dp[x]);
    }
}