T 到 4.2 光年外的半人马座去了

记录

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 25, mod = 1e9 + 7;

int n, a[N], m, b[N], dp[(1 << N)];

bool check(int num)
{
	for(int i = 1; i <= m; i++)
		if(num == b[i]) return true;
	return false;
}

signed main()
{
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	cin >> m;
	for(int i = 1; i <= m; i++)
		cin >> b[i];
	dp[0] = 1;
	for(int i = 1; i < (1 << n); i++)
	{
		int sum = 0;
		for(int j = 0; j < n; j++)
		{
			if(!((i >> j) & 1)) continue;
			sum += a[j];
		}
		if(check(sum)) continue;
		for(int j = 0; j < n; j++)
		{
			if(!((i >> j) & 1)) continue;
			if(check(sum - a[j])) continue;
			dp[i] += dp[i ^ (1 << j)] %= mod;
		}
	}
	cout << dp[(1 << n) - 1];
	return 0;
}