首页 > 代码库 > 某种密码(password.*)
某种密码(password.*)
关于某种密码有如下描述：某种密码的原文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
/* 直接暴力加剪枝60分，没想到可以先跑一半的暴力，然后用hash统计一下，再跑另一半。*/#include<cstdio>#include<iostream>#include<map>#define M 45#define ll long longusing namespace std;ll a[M],s1[M],s2[M],n,key,ans;map<ll,int> hash;void dfs(int x,int sum,int flag){ if(!flag&&x>n/2) { hash[sum]++; return; } if(flag&&x>n) { ans+=hash[key-sum]; return; } dfs(x+1,sum+a[x],flag); dfs(x+1,sum,flag);}int main(){ //freopen("jh.in","r",stdin); freopen("password.in","r",stdin); freopen("password.out","w",stdout); cin>>n>>key; for(int i=1;i<=n;i++) cin>>a[i]; dfs(1,0,0); dfs(n/2+1,0,1); cout<<ans; return 0;}
某种密码(password.*)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。