某种密码

时限1s 空间限制256m

题目描述

关于某种密码有如下描述：某种密码的原文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

一共两组可行的密文。

 

 题解: 其实有点像双向搜索，因为2^40必定tle，就不如这般搜索一下（味道更好

我们先处理前一半的加和的情况，在处理后一半加和的情况，如果两个加起来是key的话计算时一种情况了

保存加和情况的最好用hash表

（但是本宝宝实在是太弱了，就用map了

差不多就是这样的。。emm

#include <bits/stdc++.h>
#include <map>

using namespace std;

typedef long long ll;

inline ll read() {
    ll x = 0 , f = 1; char ch = getchar();
    for ( ; !isdigit(ch) ; ch = getchar()) if (ch == '-') f = -1;
    for ( ; isdigit(ch) ; ch = getchar()) x = x * 10 + ch - '0';
    return x * f;
}

const ll maxn = 50;

ll a[maxn];

ll n , key;

ll _left_geshu , _right_geshu , ans;

map <ll , ll> m;

int main() {
    n = read() , key = read();
    for (ll i = 1 ; i <= n ; i ++) {
        a[i] = read();
    }

    _left_geshu = (1 + n) >> 1 , _right_geshu = n - _left_geshu;

    for (ll i = 0 ; i < (1 << _left_geshu) ; i ++) {
        ll tmp = 0;
        for (ll j = 0 ; j < _left_geshu ; j ++) {
            if (i & (1 << j)) {
                tmp += a[j + 1];
            }
        }
        m[tmp] ++;
    }
    for (ll i = 0 ; i < (1 << _right_geshu) ; i ++) {
        ll tmp = 0;
        for (ll j = 0 ; j < _right_geshu ; j ++) {
            if (i & (1 << j)) {
                tmp += a[_left_geshu + 1 + j];
            }
        }
        if (m[key - tmp]) {
            ans += m[key - tmp];
        }
    }

    printf("%lld\n" , ans);
}