「NOIP模拟赛」某种密码

2014年10月4日3,0710

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

 

avatar
  Subscribe  
提醒