[Codeforces] 525E. Anya and Cubes

題目連結:http://codeforces.com/problemset/problem/525/E

---

一個神奇的技巧，砍半枚舉，其實就是一種枚舉的方法，不過因為可能原本$2^N$太大，所以只在兩邊各枚舉一半，變成$2^{\frac{N}{2}+1}$，不過這作法要可以有效率的枚舉出部分在左、部分在右的。像這題的話，我是先算完左半邊後，把可能的值全部塞到一個vector，sort完後，就可以在算右邊時，同時二分搜左邊可能的答案。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
#define ALL(x) (x).begin(), (x).end()
#define PB push_back
typedef pair<int,lld> PLI;

const int N = 25 + 3;

int n, k;
lld arr[N], jie[N], S, ans=0;
vector<PLI> set1;
void dfs(int,int,int,lld);
void dfs2(int,int,int,lld);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>k>>S;
	for(int i=0;i<n;i++) cin>>arr[i];
	jie[0]=1;
	for(int i=1;i<20;i++) jie[i]=jie[i-1]*i;
	int mid=n>>1;
	dfs(0, mid, k, 0);
	sort(ALL(set1));
	dfs2(mid, n, k, 0);
	cout<<ans<<'\n';
	return 0;
}

void dfs(int cur, int rg, int kk, lld sm){
	if(cur > rg or kk < 0 or sm > S) return;
	if(rg == cur){
		set1.PB({sm, k-kk});
		return;
	}
	dfs(cur+1, rg, kk, sm+arr[cur]);
	dfs(cur+1, rg, kk, sm);
	if(arr[cur] < 20) dfs(cur+1, rg, kk-1, sm+jie[arr[cur]]);
}

void dfs2(int cur, int rg, int kk, lld sm){
	if(cur > rg or kk < 0 or sm > S) return;
	if(rg == cur){
		ans += upper_bound(ALL(set1), (PLI){S-sm, kk}) - lower_bound(ALL(set1), (PLI){S-sm, 0});
		return;
	}
	dfs2(cur+1, rg, kk, sm+arr[cur]);
	dfs2(cur+1, rg, kk, sm);
	if(arr[cur] < 20) dfs2(cur+1, rg, kk-1, sm+jie[arr[cur]]);
}