自动搬运

查看原文

来自洛谷，原作者为

	TemplateClass **

搬运于2025-08-24 22:00:42，当前版本为作者最后更新于2025-06-26 20:34:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

给出一个跑得很慢而且不保证在当年的评测机上能跑过的算法。

Update 2025/07/09：对代码进行了一点优化，现在应该可以了。

我们考虑用一个 unsigned long long（简称 key）把 $10$ 个人的状态压一块，具体的，我们给每一个人分配 $5$ 位表示这个人一共完成了多少件事。

然后我们从这个 key 等于 $0$ 开始 dfs，每次取出这个人下一次可以完成的事件，然后枚举子集，对于每个子集检查是否有相关联的事件如果有就跳过，更新 key 后用新的 key 接着 dfs，用容斥原理更新一下答案即可。

但是这样你会发现你完全过不了，考虑用一个 map 记录每次 dfs 的结果然后记忆化，但还是过不了，把 map 换成 unordered_map 即可。

虽然现在能过但是最大点将近 5s，注意到这题空间限制比较大，我们可以提前给这个 unordered_map 进行一个大小为 $T$ 的 reserve，这样最大点只有 4s 多一点了。

时间复杂度 $O(T 2 ^ N N ^ 2)$。

这是我原本写的代码（别急，看完这个代码后下面还有我新想到的优化）：Link。

现在我惊奇地发现，如果你把用 dep 判断冲突这部分进行一点小转化，变成位运算，那么对时间有惊人的优化，即把读入改成：

for(int i = 0; i < m; ++i) for(int j = 0; j < m; ++j) 
	{ bool x; std::cin >> x; x ? dep[i] |= (1ull << j) : 0; }

然后判断改成：

for(int t = s; t; t &= t - 1) {
	if(mskt & dep[ev[__builtin_ctz(t)].second]) { f = false; break; }
	else mskt |= (1ull << ev[__builtin_ctz(t)].second);
}

现在的最大点只有 1.5s 的样子了，最后放一下真正的最终代码（也不一定，说不定我哪天又想到什么优化了呢），这里面加了一点上面没提到的优化，不过也不难看懂：

typedef unsigned long long ull;
typedef std::pair<int, int> pr;
constexpr int N = 10 + 1, M = 15 + 1, B = 5, T = 1e6;

int n, m; std::vector<int> q[N];
std::unordered_map<ull, int> mp;
ull msk = (1ull << B) - 1, fkey = 0, dep[N];

int dfs(ull key){
	if(key == fkey) return 1;
	if(mp.count(key)) return mp[key];
	int sz = 0; pr ev[N];
	for(int i = 0; i < n; ++i) {
		ull pgs = (key >> (B * i)) & msk;
		if(pgs < q[i].size()) ev[sz++] = pr(i, q[i][pgs]);
	}
	int smx = (1 << sz), res = 0;
	for(int s = 1; s < smx; ++s) { bool f = true; ull mskt = 0;
		for(int t = s; t; t &= t - 1) {
			if(mskt & dep[ev[__builtin_ctz(t)].second]) { f = false; break; }
			else mskt |= (1ull << ev[__builtin_ctz(t)].second);
		}
		if(!f) continue; ull nkey = key;
		for(int i = 0; i < sz; ++i) if(s & (1 << i))
			nkey += (1ull << (B * ev[i].first));
		(__builtin_popcount(s) & 1) ? res += dfs(nkey) : res -= dfs(nkey);
	}
	return mp[key] = res;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0), std::cout.tie(0);
	
	std::cin >> n >> m;
	for(int i = 0; i < n; ++i) {
		int c; std::cin >> c; for(int j = 0; j < c; ++j)
		{ int x; std::cin >> x; q[i].push_back(x); }
	}
	for(int i = 0; i < m; ++i) for(int j = 0; j < m; ++j) 
	{ bool x; std::cin >> x; x ? dep[i] |= (1ull << j) : 0; }
	for(int i = 0; i < n; ++i) fkey |= (ull(q[i].size()) << (B * i));
	mp.reserve(T); std::cout << dfs(0);
	
	return 0;
}