关于某种密码有如下描述：某种密码的原文A是由N个数字组成，而密文B是一个长度为N的01数串，原文和密文的关联在于一个钥匙码KEY。若KEY=∑▒〖Ai*Bi〗，则密文就是原文的一组合法密码。

现在有原文和钥匙码，请编一个程序来帮助他统计到底有多少个符合条件的密文。

「输入数据」

第一行两个数N，KEY，意义同题目描述；

第二行N个数表示原文A，意义同题目描述。

「输出数据」

一个数ANS，表示对于原文A和KEY，有多少组可行的密文B。

「输入样例」

3 2

1 1 2

「输出样例」

2

「样例说明」

密文110，1*1+1*1+0*2=2

密文001，0*1+0*1+1*2=2

一共两组可行的密文。

「数据约定」

60%数据满足N<=25

100%数据满足N<=40，-maxlongint<=∑▒Ai<=maxlongint

题解

由于sum{a[i]}太大所以不考虑背包

可以把n个数分成两半搜索。。。

然后用个哈希表或者map