这题就是个快速沃尔什变换的模板题，输入ai时，令s[ai]=1，对s[]做一遍DWT_AND(s)（快速沃尔什正变换，按位与），然后直接访问s[x]完事。
#include<map> #include<queue> #include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define MAXN 10000005 #define LL long long #define DB double #define ENDL putchar('\n') #define lowbit(x) ((-x)&(x)) LL read() { LL f = 1,x = 0;char s = getchar(); while(s < '0' || s > '9') {if(s=='-')f=-f;s = getchar();} while(s >= '0' && s <= '9') {x=x*10+(s-'0');s=getchar();} return f*x; } const int MOD = 998244353; const int N = 1048576; int n,m,i,j,s,o,k; bool a[N+5]; void DWT_AND(bool *s) { for(int k = 1;k < N;k <<= 1) { for(int i = 0;i < N;i += (k<<1)) { for(int j = i;j < i+k;j ++) { s[j] |= s[j+k]; } } } return ; } int main() { n = read();m = read(); for(int i = 1;i <= n;i ++) { s = read(); a[s] = 1; } DWT_AND(a); for(int i = 1;i <= m;i ++) { s = read(); printf(a[s] ? "yes\n":"no\n"); } return 0; }
