题解：AT_arc140_d [ARC140D] One to One

· · 题解

2024 年 10 月 31 日：修改状态、转移方程、统计答案部分的文字表述，以及转移方程的公式错误。\ 2024 年 11 月 11 日：更详细地解释式子的含义。

题面翻译

你有一个长度为 n 的序列 a_1,a_2,\dots,a_n，其中每个元素都是 [1,n] 中的整数。

初始时有编号为 1 \sim n 的 n 个节点，对于每个 1\leq i \leq n，从 i 向 a_i 连一条无向边。a_i=-1 表示 a_i 还没有确定。你需要对所有可能的 a 序列求出图中连通块数量的和对 998244353 取模的结果。

题目讲解

注意到一个美妙的性质。\ 先把所有不是 -1 的点 i 向 a_i 连边（可以先假设为有向边，更好理解），会发现每一个连通块是树、环或者基环树。\ 环和基环树内一定没有 -1 的点，用有向图的思维可以理解为内向树。\ 至于树，-1 的点只有一个，并且它是根节点。

因此确定完所有 -1 点的连接状态之后，整个图会变成若干个基环树和环。

发现性质之后就是神仙计数题了，设有 m 个树连通块。\ 对于基环树和环而言，往它们连边后树不计算贡献，所以可以单独计算它们自己的贡献，根据乘法原理，每个基环树和环贡献是 n^m。

发现 n 很小，可以设二维状态。\ 设 dp_{i,j} 表示前 i 个树连通块，选择 j 个使得他们组成一个基环树或环的方案数，则有：

dp_{i,j}=dp_{i-1,j-1} \times siz_{i} + dp_{i-1,j}

其中 siz_{i} 表示第 i 个树连通块的大小。\ 前者表示选择 i 这一树连通块，与当前已组成的连通块合并有 sz_i 种方法。\ 换句话说，设 j 个联通块的顶点集合为 S，则一个环的方案数是 \prod_{v \in S} sz_v。而当前选 i，则表示该环要多一个元素 i，也即方案数要乘上 sz_i。\ 后者表示不选择 i，直接从前 i-1 个选 j 个的状态转移而来。

考虑如何统计答案。基环树和环的答案已经统计过了，而我们现在要统计树连通块的贡献。

ans = \sum\limits_{i=1}^{m} dp_{m,i} \times n^{m-i} \times (i-1)!

它的意思是，从 m 个树连通块中选择了 i 个组成一个连通块， i 个连通块本身则有 i! 种排列方式，但由于这个环是可以循环位移（旋转）的，所以方案数量是 \frac{i!}{i}=(i-1)!，即 dp_{m,i} \times (i-1)!。\ 而其余的 m-i 个树连通块的根节点可以连接到任意一个点，与之合并成同一连通块，贡献是 n^{m-i}。注意这种情况并不会对连通块个数有 +1 的贡献，但是它们可以任意选择 n 个节点中的一个进行连接，所以会把 dp_{i,j} 的答案乘上 n^{m-i}，即只考虑当前钦定的这个连通块所产生的贡献。

略微提一下，这样的状态设计就已经能过了，不过当然可以把 DP 压缩到一维，倒序转移，这和背包是类似的。\ 注意开 long long。

时间复杂度 O(N^2)，码风可能比较抽象请见谅。

#include <bits/stdc++.h>
using namespace std;
const int N = 2015, M = N << 1;
const int mod = 998244353;
int n, a[N], dp[N][N];
int h[N], e[M], ne[M], idx = 0;
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool st[N];
int sz[N];
void dfs(int u, int root) {
    st[u] = 1, sz[root]++;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (st[v]) continue;
        dfs(v, root);
    }
}

int m, b[N], fac[N];

int qmi(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = (res * 1ll * a) % mod;
        a = (a * 1ll * a) % mod;
        k >>= 1;
    }
    return res;
}

int main() {
    scanf("%d", &n);
    fac[0] = 1;
    for (int i = 1; i <= n; i++) h[i] = -1, fac[i] = (fac[i - 1] * 1ll * i) % mod;

    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if (a[i] != -1) add(i, a[i]), add(a[i], i);
    }
    for (int i = 1; i <= n; i++)
        if (a[i] == -1) dfs(i, i), b[++m] = i;
    dp[0][0] = 1;
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j <= i; j++)
            dp[i][j] = ((dp[i - 1][j - 1] * 1ll * sz[b[i]]) % mod + dp[i - 1][j]) % mod;
    }
    long long ans = 0;
    for (int i = 1; i <= m; i++)
        (ans += ((dp[m][i] * 1ll * fac[i - 1]) % mod * 1ll * qmi(n, m - i)) % mod) %= mod;  //树之间的连边

    for (int i = 1; i <= n; i++)
        if (!st[i]) dfs(i, i), (ans += qmi(n, m)) %= mod;   //基环树连通块

    printf("%lld\n", ans);
    return 0;
}