题解：P4489 [CTSC2009] 纷繁世界

· · 题解

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

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;
}