关于某种密码有如下描述：某种密码的原文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
/*
这道题作为第一题难度确实是不大，但一定要有这个优化的意识，如果纯粹搜索所有方案，时间无法承受，我们可以考虑到，当前面一些的值计算出来，后面的值等于说是在前面的基础上进行进一步的计算，我们于是考虑到去掉“在前面的基础上”这个指数级的冗余运算，通过后面和前面比较，先算前面的，后面的看有没有那个和他相加等于K的就行了，hash运算，注意sum可能是一个很大的负数
*/
//我写的hash
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#define ll long long
#define fo(i,l,r) for(int i = l;i <= r;i++)
using namespace std;
const ll sed = ,Sed = ,mod = ,Mod = ;
struct dat{
ll v;
ll a;
};
int n;
bool gt;
vector<dat> h[mod];
ll a[],key,ans,lm;
inline void dfs(int pos,ll sum){
if(pos <= lm){
dfs(pos+,sum+a[pos]);
dfs(pos+,sum);
}else{
dat tmp;
if(!gt) {
ll ha = (sum + mod*) % mod;
ll hb = (sum + Mod*) % Mod;
for(int i = ;i < h[ha].size();i++){
if(h[ha][i].v == hb){
h[ha][i].a++;
return;
}
}
tmp.v = hb;
tmp.a = ;
h[ha].push_back(tmp);
}else{
ll ha = (key - sum + mod*) % mod;
ll hb = (key - sum + Mod*) % Mod;
for(int i = ;i < h[ha].size();i++){
if(h[ha][i].v == hb){
ans+=h[ha][i].a;
break;
}
}
} }
}
int main(){
freopen("password.in","r",stdin);
freopen("password.out","w",stdout);
cin>>n>>key;
fo(i,,n){
cin>>a[i];
}
if(n == ){
ans = (a[] == key) + ( == key);
return ;
}
lm = n >> ;
dfs(,);
gt = true;
lm = n;
dfs((n >> )+,);
cout<<ans;
return ;
}
//黄学长Map
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
#define ll long long
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
bool flag;
ll ans;
int n,cnt,key;
int a[];
map<int,int> b;
void dfs(int x,int now)
{
if(x==cnt+)
{
if(!flag)b[now]++;
else ans+=b[key-now];
return;
}
dfs(x+,now+a[x]);
dfs(x+,now);
}
int main()
{
//freopen("password.in","r",stdin);
//freopen("password.out","w",stdout);
n=read();key=read();
for(int i=;i<=n;i++)
a[i]=read();
cnt=n/;dfs(,);
flag=;cnt=n;dfs(n/+,);
printf("%I64d",ans);
return ;
}