【NOIP模拟赛】某种密码

2014年10月4日1,4080

关于某种密码有如下描述:某种密码的原文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