题面
题目描述（就挺抽象的）
$feluamn$ 所在的世界陷入了永恒之夜。本属于光明的他们，如今只能在黑暗中苟且为生。
精灵一族信任与她的善良、勇敢与坚韧，$feluamn$ 得知了划破这黑暗的唯一方法。那就是登上光明之巅！只有 $feluamn$ 这么可爱又善良的女孩子，才有可能成功。
为了拯救这即将凋零的世界，$feluamn$ 整理行囊，准备踏上行程。
$feluamn$ 需要一些魔力晶板来驱散路途的黑暗。现在 $feluamn$ 有 $n$ 块魔力晶板，每块晶板上有 $m$ 个魔力槽，从 $1$ 到 $m$ 标号。一些魔力槽中可能有魔力水晶。$feluamn$ 需要第 $a1,a2,⋯,ak$ 个位置上有魔力水晶，而其他位置没有水晶的魔力晶板。所以她需要取下一些魔力水晶。由于黑暗诅咒的关系，当第 $i$ 个位置的水晶被取下后，第 $i+b1,i+b2,⋯,i+bc$ 个位置上的魔力水晶也会随之掉落。特别的，如果 $i+b1,i+b2,⋯,i+bc$ 的某个位置上没有魔力水晶，这个魔力水晶就不能被取下。并且水晶一旦离开魔力晶板就无法再安装上去了。
$feluamn$ 希望能有尽量多的魔力晶板，以备旅途上的不测。由于空间水晶的存在，$feluamn$ 并不需要担心衣兜不够大。但她忙于将 $FMT$ （鬼知道FMT是什么玩意） 融会贯通，以更好地对付黑暗，并没有时间来考虑这个问题。如果你能告诉她答案，这个可爱又善良的女孩子会对你感激不尽。
输入描述
为了便于输入输出，约定用一个十进制整数来表示魔力晶板的状态。这个整数的二进制下第 i 位为 1 ，则表示魔力晶板的第 i+1 个位置有魔力水晶，反之则没有。
第一行一个正整数 T ，表示数据组数。
对于每组数据，第一行两个正整数 n,m ，意义如问题描述中所述。
接下来 n 行，每行一个整数 x 表示 feluamn 拥有的魔力晶板的状态。
接下来一行一个非负整数 c ，意义如问题描述中所述。
接下来一行 c 个正整数，第 i 个正整数表示 bi 。
接下来一行一个正整数 q ，表示询问数量。接下来 q 行，每行一个非负整数表示 feluamn 所需的魔力晶板的状态。
输出描述
对于每组数据，输出 q 行。第 i 行一个非负整数表示第 i 个询问的答案。注意不同的数据之间不需要用空行隔开。
样例数据
见此
数据范围
对于所有数据，T≤5,1≤q,n≤100000,1≤m≤20,1≤bi≤m,c<m 。保证代表魔力晶板状态的整数不超过 m 位。相同的 bi 只算一个。
对于20% 的数据：1≤q,n≤1000
对于另外20% 的数据：1≤m≤7
对于另外30% 的数据：c=0
对于另外40% 的数据：没有特殊限制
题解
首先，我们可以发现 $b$ 这个数组完全可以用一个十进制数表示（因为这个题目的其他输入都是用十进制数表示的），设这个数为 $ans$，那么显然有：
| $ans | =(1«b_{i})$ |
其中 $ans$ 的初始值为 $1$。它表示在 $1$ 号位去掉魔力水晶时，实际会去掉的水晶。
但是显然，不只有 $1$ 号位可以进行去掉水晶的操作，任何位置都可以（当然，要合法）。这也简单，只需要将 $ans$ 左移 $j$ 位，就可以表示在 $(1+j)$ 位进行操作。那么，我们让 $j$ 从 $0$ 不断递增，直到不可行为止。
判断不可行的方式是：如果 $ans$ 左移 $j$ 位后比最大的 $x$ 还要大，那么显然不可行，即当:
$ans«j>x_{max}$ 时结束。
注意，$j$ 必须从小到大，如果从大到小的话会有重复情况。
那么如何判断是否合法？
首先，我们要明确不合法的情况。当那个位置上没有魔力水晶时，你还进行去掉的操作，那就是不合法的。
由于 $x$ 与 $ans$ 的二进制中， $1$ 表示有，而 $0$ 表示没有，所以如果 $x$ 和 $ans$ 进行按位与运算，结果仍是 $x$ 的话，就说明 $ans$ 包含于 $x$ ，即合法。即当：
ans&x==ans时合法，否则不合法。
接下来就简单了,令 $f_{i}$ 表示能到状态 $i$ 的魔力晶板个数，那么显然有：
$f_{i-ans«j+1}=f_{i-ans«j+1}+f_{i}$
最后对于每个询问 $qus$ 直接输出 $f_{qus}$ 即可。
代码中，用 $t$ 数组来表示 $ans$ 左移 $j$ 位 （$t_{j+1}=ans«j$)，$tlen$ 为目前 $t$ 数组的长度，即 $j+1$ ; $maxn$ 表示 $x_{max}$ 。 $f$ 数组的初值为 $f[x_{i}]=1$ ，其余位置为 $0$ ；$k$ 表示每个被输入的 $b_{i}$ 。
好了，请食用下面这份代码：
#include<bits/stdc++.h>
using namespace std;
inline int read()//快读函数，可以快速读取（输入）
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
return s*w;
}
const int N=25;
const int NN=1e6+114514;
int f[NN],t[N];
int main()
{
int T;
T=read();
while(T--)
{
int tlen=1;
memset(f,0,sizeof(f));
int m,n,q,c,maxn=0,ans=1;
n=read();
m=read();
for(int i=1;i<=n;i++)
{
int x;
x=read();
f[x]++;
maxn=max(maxn,x);
}
c=read();
for(int i=1;i<=c;i++)
{
int k;
k=read();
ans|=(1<<k);
}
t[1]=ans;
while(t[tlen]<=maxn)
{
for(int i=maxn;i>=t[tlen];i--)
{
if((i&t[tlen])==t[tlen]) f[i-t[tlen]]+=f[i];
}
t[tlen+1]=(t[tlen]<<1);
tlen++;
}
q=read();
for(int i=1;i<=q;i++)
{
int qus;
qus=read();
printf("%d\n",f[qus]);
}
}
}
这道题的出题者实在是天才。
还有人说高维前缀和、$FMT$ 也可以做，就留给大家研究了。