题面

题目描述（就挺抽象的）

$feluamn$ 所在的世界陷入了永恒之夜。本属于光明的他们，如今只能在黑暗中苟且为生。

精灵一族信任与她的善良、勇敢与坚韧，$feluamn$ 得知了划破这黑暗的唯一方法。那就是登上光明之巅！只有 $feluamn$ 这么可爱又善良的女孩子，才有可能成功。

为了拯救这即将凋零的世界，$feluamn$ 整理行囊，准备踏上行程。

$feluamn$ 需要一些魔力晶板来驱散路途的黑暗。现在 $feluamn$ 有 $n$ 块魔力晶板，每块晶板上有 $m$ 个魔力槽，从 $1$ 到 $m$ 标号。一些魔力槽中可能有魔力水晶。$feluamn$ 需要第 $a1,a2,\cdots ,ak$ 个位置上有魔力水晶，而其他位置没有水晶的魔力晶板。所以她需要取下一些魔力水晶。由于黑暗诅咒的关系，当第 $i$ 个位置的水晶被取下后，第 $i+b1,i+b2,\cdots ,i+bc$ 个位置上的魔力水晶也会随之掉落。特别的，如果 $i+b1,i+b2,\cdots ,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$。它表示在 $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$ 也可以做，就留给大家研究了。