Brief description :
卡搜索，卡DP的子集和问题。
(N<=40, M<=1,000,000,000)
Analyse :
存在着一种折衷的办法，即将折半搜索出两张散列表，再拼接。
复杂度是 O(2^20) ，勉强可以卡过它。
/*
Author: xiaodao
Prog: HOJ 2963. Count Subset
Status: Accepted
Last modifiy: GMT +8 Aug. 29th 17:49
*/
#include
#include
const int PRIME = 3214567; //4500989
const int N = 40;
struct node{
int k, s;
} hash[PRIME];
int n, step; int a[N];
long long m, ans;
int h(int k){
return (k % PRIME);
}
int Search(int k){
int y = h(k);
while (hash[y].k != k && hash[y].s!=0)
y = (y+1) % PRIME;
return y;
}
void Insert(int k){
node &y = hash[Search(k)];
y.k = k; y.s++;
}
void dfs1(int k, long long s){
if (s>m) return;
if (k==step) Insert(s);
else{
dfs1(k+1, s+a[k]);
dfs1(k+1, s);
}
}
void dfs2(int k, long long s){
if (s>m) return;
if (k==step) ans += hash[Search(m-s)].s;
else{
dfs2(k+1, s+a[k]);
dfs2(k+1, s);
}
}
void solve(){
step = n/2; dfs1(0, 0);
step = n; dfs2(n/2, 0);
}
void init(){
scanf("%d", &n);
int x, y;
for (int i=0;i
Hit :
此题内存供应比较紧张，要注意一下几个方面。
1. iostream 会消耗1000KB的空间，stdio.c 消耗的空间比 cstdio 的空间要多。
2. 只开一张散列表。（也就是第二次搜索到叶子结点的时候直接在先前的散列表中查询了。）
3. 采用简单的闭散列。（其实理论分析这种方法虽然有助于固定内存，但应该对总的内存访问量没有帮助，
不过考虑到也许系统没有办法立即释放掉指针的内存。）
因此我手写了一个线性探查的闭散列，注意到如果用STL::MAP，无论我怎么写都要 MLE 。
