记录编号	488372	评测结果	AAAAAAAAAA
题目名称	博士的密码	最终得分	100
用户昵称	HtBest	是否通过	通过
代码语言	C++	运行时间	0.119 s
提交时间	2018-02-21 08:43:03	内存使用	24.31 MiB

#define _CRT_SECURE_NO_DEPRECATE
/************************
 *创建时间：2018 02 20
 *文件类型：源代码文件
 *题目来源：2018寒假·NOI导刊
 *采用算法：分治、搜索
 *作者：HtBest
 ************************/
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <string.h>
// #include <stack>
// #include <queue>
#include <map>
// #include <set>
// #include <vector>
// #include <ctype.h>
// #include <math.h>
// #include <bits/stdc++.h>
using namespace std;
int n,key,a[50],flag,_dic[3]={0};
long long dic[3][1<<20],counts=0;
map <long long, int> ans[3];
/*------------------------------声明变量------------------------------*/
/* Variable explain:
 
 */
void dfs(int head,int tail,int value)
{
    if(head==tail)
    {
        if(ans[flag][value]==0)
            dic[flag][_dic[flag]++]=value;
        ans[flag][value]++;
        return;
    }
    dfs(head+1,tail,value);
    dfs(head+1,tail,value+a[head]);
    return;
}
int main()
{
    freopen("password1.in","r",stdin);
    freopen("password1.out","w",stdout);
    scanf("%d%d",&n,&key);
    for(int i=0;i<n;++i)    scanf("%d",&a[i]);
    flag=0;    dfs(0,n>>1,0);
    flag=1;    dfs(n>>1,n,0);
    for(int i=0;i<_dic[0];++i)
    {
        for(int j=0;j<_dic[1];++j)
        {
            int ls1=dic[0][i],ls2=dic[1][j];
            if (ls1+ls2==key)
            {
                // printf("Found:%d + %d = %d ,add %d * %d\n",ls1,ls2,key,ans[0][ls1],ans[1][ls2]);
                counts+=ans[0][ls1]*ans[1][ls2];
            }
        }
    }
    printf("%lld",counts);
    return 0;
}