数学 Trick 之：宽限+反演

porse · 2025-04-19 11:25:07 · 算法·理论

能够解决的问题

有不好刻画/转移的勾石限制的一些问题。

优缺点

优点：代码简单，且这一类基本上都是区分度高的题。

缺点：适用性不广泛。

思路

既然有勾石限制，那我们就宽限！

1. 我们可以尝试将限制变简单，然后就可以考虑能否反演。

注：此时一定不要想着这个新限制能否转移，否则大脑容易焦虑，退缩，只管推反演就行了。

2. 当我们发现一个能反演的更简单的性质了，我们可以考虑转移，然后：

• 如果 TLE，就再放宽。
• 实在放不宽，果断放弃。

思路比较抽象，我们通过一个具体例题来讲。

例题与代码

P3349 [ZJOI2016] 小星星

这道题中恶心的限制在于：

• 必须与原图一一对应（不重不漏用每个点）。

那么我们就可以考虑放宽一点，既然单射太难，那么就多射，变为：

• 原图每个点都唯一对应树上的点集 S。

此时，我们可以列出状态 dp_{u,S} 表示 u 的子树中，可以重复的用点集 S 的点对应。

我们发现这样不好转移，因为我们无法得知图中转移边（即父亲与儿子对应点间的边）的有无，所以我们加一维： dp_{u, j, S} 表示 u 的子树中，u 对应 j，可以重复的用点集 S 的点对应。

那么我们有（不要问我怎么推出来的，都这个程度了）：

时间复杂度 O(n^32^n)，这题需要卡常，60\text{pts} 就够了。

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

#define int long long
constexpr int maxn = 18, maxk = 131072;

int n, m, a, b, dp[maxn][maxn][maxk], G[maxn][maxn], g[maxk], f[maxk], ans, K, sz[maxk];
vector <int> T[maxn];

int kth(int S, int k) {
    return ((S >> (k - 1)) & 1);
}
int siz(int S) {
    int ress = 0;
    for (int i = 1; i <= n; i++) {
        ress += kth(S, i);
    }
    return ress;
}

void dfs(int t, int g, int fa, int S) {
    if (dp[t][g][S]) return ;
    dp[t][g][S] = 1;
    int nowsum;
    for (int now : T[t]) {
        if (now == fa) continue;
        nowsum = 0;
        for (int i = 1; i <= n; i++) {
            if (kth(S, i) && G[g][i]) {
                dfs(now, i, t, S);
                nowsum += dp[now][i][S];
            }
        }
        dp[t][g][S] *= nowsum;
    }
    return ;
}

int p(int x) {
    return ((x & 1) ? -1 : 1);
}

signed main() {
    input.read(n, m);
    K = (1 << n);
    for (int S = 0; S < K; S++) {
        sz[S] = siz(S); 
    }
    for (int i = 1; i <= m; i++) {
        input.read(a, b);
        G[a][b] = G[b][a] = 1;
    }
    for (int i = 1; i < n; i++) {
        input.read(a, b);
        T[a].push_back(b);
        T[b].push_back(a);
    }
    for (int j = 1; j <= n; j++) {
        for (int S = 0; S < K; S++) {
            if (!kth(S, j)) continue;
            dfs(1, j, 0, S);
        }
    }

    for (int S = 0; S < K; S++) {
        for (int i = 1; i <= n; i++) {
            if (!kth(S, i)) continue;
            g[S] += dp[1][i][S];
        }
    }

    for (int S = 0; S < K; S++) {
        ans += p(n - sz[S]) * g[S];
    }

    output.write(ans, '\n');

    return 0;
}