[FZOJ1552] 某种密码 (password.*)

2014-10-20
竞赛题解 / 搜索
DFSFZOJ

描述 Description

关于某种密码有如下描述：某种密码的原文 A 是由 N 个数字组成，而密文 B 是一个长度为 N 的 01 数串，原文和密文的关联在于一个钥匙码 KEY。若 KEY=∑〖Ai*Bi〗，则密文就是原文的一组合法密码。

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

输入格式 InputFormat

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

输出格式 OutputFormat

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

样例输入 SampleInput

3 2
1 1 2

样例输出 SampleOutput

2

来源 Source

2014-10-4NOIP 模拟赛 by lwher

FZOJ 1552

代码 Code

分为前 n/2 和后 n/2 位分开搜索，哈希判断。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
int key;
long long ans;
int a[45];
map <int,int> mp;
void dfs(int s)
{
    int i,j,t;
    if (s==(n>>1))
    {
        mp[m]++;mp[m+a[s]]++;
        return ;
    }
    if (s==n)
    {
        ans+=mp[key-m]+mp[key-m-a[s]];
        return ;
    }
    m+=a[s];
    dfs(s+1);
    m-=a[s];
    dfs(s+1);
}
int main()
{
    freopen("password.in","r",stdin);
    freopen("password.out","w",stdout);
    scanf("%d%d",&n,&key);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    ans=m=0;
    dfs(1);
    ans=m=0;
    dfs((n>>1)+1);
    printf("%lld\n",ans);
    return 0;
}