描述

关于某种密码有如下描述：某种密码的原文A是由N个数字组成，而密文B是一个长度为N的01数串，原文和密文的关联在于一个钥匙码KEY。

若KEY=∑(Ai∗Bi)KEY=∑(Ai∗Bi)，则密文就是原文的一组合法密码。

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

输入

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

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

输出

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

样例输入

3 2

1 1 2

样例输出

2

提示

【样例说明】

密文110，1∗1+1∗1+0∗2=21∗1+1∗1+0∗2=2

密文001，0∗1+0∗1+1∗2=20∗1+0∗1+1∗2=2

一共两组可行的密文。

【数据约定】

60%数据满足N<=25

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

发现对于两个区间

两边搜到的值是可以拼起来的

所以就双向搜索

用个map来记录答案

加上前缀正、负和剪枝

#include
    
     #include
     
      using namespace std;#define int long long#define ll long long inline int read(){
    	char ch=getchar();	int res=0,f=1;	while(!isdigit(ch)){
    if(ch=='-')f=-1;ch=getchar();}	while(isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();	return res*f;}tr1::unordered_map
      
        mp;tr1::unordered_map
       
         np;int n,m,a[50],pre[50],nec[50],ans,sum1[1500005],cnt;void dfs(int pos,ll sum){
    	if(pos>n){
    		if(sum==m)ans++;		return;	}	if(sum+pre[pos]
        
         m){
    		return;	}	dfs(pos+1,sum);	dfs(pos+1,sum+a[pos]);}void dfs1(int pos,ll sum){
    	if((sum+pre[pos]
         
          m)){ return; } if(pos>(n/2)){ if(!mp[sum])sum1[++cnt]=sum; mp[sum]++; return; } dfs1(pos+1,sum); dfs1(pos+1,sum+a[pos]);}void dfs2(int pos,ll sum){ if((sum+(pre[1]-pre[pos+1])
          
           m)){ return; } if(pos<=n/2){ np[sum]++; return; } dfs2(pos-1,sum); dfs2(pos-1,sum+a[pos]);}signed main(){ n=read(),m=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=n;i>=1;i--)(a[i]>0)?pre[i]=pre[i+1]+a[i]:pre[i]=pre[i+1]; for(int i=n;i>=1;i--)(a[i]<0)?nec[i]=nec[i+1]+a[i]:nec[i]=nec[i+1]; if(n<=25){ dfs(1,0); cout<