C++ 解法, 执行用时: 116ms, 内存消耗: 932K, 提交时间: 2022-03-18 20:08:40

#include <iostream>
#include <algorithm>
#include <cstring>
typedef long long ll;
using namespace std;
const int N = 20, M = 1e3 + 10;
const ll P = 1e9 + 7;
int n, m, k, s, ned[N], c[M], bo[1 << 16];
ll f[N][M], ans[M];
int count(int x)
{
	int cnt = 0;
	while (x)
	{
		if (x & 1) cnt++;
		x >>= 1;
	}
	return cnt;
}
int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		cin >> n >> m >> k >> s;
		memset(ned, 0, sizeof(ned));
		memset(ans, 0, sizeof(ans));
		memset(f, 0, sizeof(f));
		memset(bo, 0, sizeof(bo));
		memset(c, 0, sizeof(c));
		for (int i = 1; i <= s; i++) cin >> c[i], c[i] += c[i - 1];
		for (int i = 0, u, v; i < k; i++)
		{
			cin >> u >> v;
			u--, v--;
			ned[v] |= (1 << u);
		}
		f[0][0] = 1;
		for (int i = 0; i < n; i++)
			for (int j = 0; j <= m; j++)
				if (f[i][j] > 0) for (int k = 1; k <= s; k++)
					if (j + c[k] <= m)
						f[i + 1][j + c[k]] = (f[i + 1][j + c[k]] + f[i][j]) % P;
					else break;
		bo[0] = 1;		    
		for (int i = 0; i < (1 << n); i = -(~i))
			if (bo[i]) for (int j = 0; j < n; j = -(~j))
				if (!(i & (1 << j)) && (ned[j] & i) == ned[j])
					bo[i ^ (1 << j)] = 1;
		for (int i = 0; i < (1 << n); i++)
		{
			if (!bo[i]) continue;
			int cnt = count(i);
			for (int j = 1; j <= m; j++)
				ans[j] = (ans[j] + f[cnt][j]) % P;
		}
		for (int i = 1; i <= m; i++) cout << ans[i] << " ";
		puts("");
	}
	return 0;
}