Fate

· · 题解

P11563 【MX-X7-T4】[LSOT-3] 命运

题意

给定一个长度为 n 的序列 p_1, \ldots, p_n（未必为排列），保证 1 \le p_i \le n。求满足以下条件的排列 a_1, \ldots, a_n 的个数，对 998244353 取模：

对每个 1 \le i \le n，都有 a_i=p_i 或者 a_{p_i}=i 成立。

分析

评价为比较综合和复杂的计数题，难度不止蓝，没有做出来。由于笔者做了很久，所以这篇题解会比较废话。

虽然题目描述很抽象，完全不懂在说什么，但是可以明显看出来一定的图论倾向 。

会被第 i 个事件影响的是第 a_i 个事件

经历了第 i 个事件后影响了事件 p_i

我们将 p_i 和 a_i 看作是点 i 的一条边，我们可以将序列 p 和 a 分别转化成基环树森林 。

记 p 得到基环树森林 P ， a 得到 A 。

对每个 1 \le i \le n，都有 a_i = p_i 或者 a_{p_i} = i 成立 。

我们分析这个条件在 P 和 A 之间建立了何种联系 。

对于 P 中的一条边 i \to p_i ，A 中需要存在一条边 i \to p_i 或者 p_i \to i 。

也就是说 P 中的方向并不重要，我们将 P 当作无向图处理， 但是 A 还需要是有向图，毕竟我们要对 a 计数，不能舍弃原排列 a 中带来的方向信息 。

注意到 a 是一个排列，可以推导得到对于 A 中的任意一点 u ，u 的入度至多为 1 ，出度至多为 1 。

由于 P 的每条边都要在 A 中对应，所以 P 的每个点的度数也不能超过 2 ，否则无解。

而 P 还是基环树森林，所以 P 的每个联通块都是环 ？

并非如此，如果 P 中出现了重边，由 p_i = j, p_j = i 生成 i \to j,j \to i ，这种情况下，由于我们将 P 视作无向图，所以重边并不会导致实际上度数的增加。

所以 P 的联通块除了环以外，还可以是一个链上带重边，或者说二元环。

如图所示

我们考虑对 P 中的每一个联通块，对 A 中的对应联通块进行计数。

先考虑 P 中的环，它在 A 中也必然是一个相应的环，但是 A 是有向图，我们还要考虑边的方向。由于每个点只有一个出度和一个入度，所以整个环的方向是相同的，整体要么呈顺时针，要么呈逆时针。记 P 中有个 y 个环，它们会产生 2^y 的方案数。

然后是 P 中的链，类似地，我们要对 A 中的的链进行定向，但是注意到，一条链的头部缺乏一个出度，尾部缺乏一个入度。我们可以让头部自由地连向其他链的尾部，或者自己的尾部，让自己也变成一个环。

记 P 中有 x 个链，它们产生的方案数是 2^x \cdot x! ，其中 2 的幂来自于不同方向，阶乘来自于链的不同拼接的方案数。

容斥

但是还没完，我们还遗漏了一个点 。

在 P 中可能会出现如图的独立的二元环结构，由于我们认为 P 是一个无向图，然后就会变成一个长度为 2 的链 。

在上述的计数过程中，如果这个长度为 2 的链，我们对其进行两次定向，然后发生了 “自交” ，就会产生

这其实是本质相同的一种方案，我们应想办法排除 。

以下我们来仔细地处理链的部分的方案数 。

我们记 f(d) 为恰好 d 个二元环的情况下链的部分的答案的方案数 。

而链的部分的答案就是

s = \sum_{i=0}^k f(i)

通常而言，“恰好” 是不好计算的，而 “钦定” 是好计算的 。我们记 g(d) 为钦定 d 个二元环的情况下链的部分的答案的方案数 ，也就是我们任意选取 d 个长度为 2 的链 ，要求这 d 条链自交，其余的链我们仍视作普通的链进行处理。

那么 g 就很好计算了，容易得到

g(d)=\binom{k}{d} 2^{x-d} (x-d)!

但是 “钦定” 和 “恰好” 是差得远的，当我们钦定 d 个二元环时，实际上包含了很多 \ge d 的恰好的情况。

我们可以推得它们之间的关系是

g(d)=\sum_{i=d}^k \binom{i}{d} 2^{i-d} f(i)

而如果我们不考虑二元环，也就是上文我们原先的算法，答案就是 g(0) 。

容斥的一个很重要的功能就是建立“钦定”与“恰好”之间的联系 ，我们考虑使用容斥。

一般来讲我们可以用容斥计算 “满足任意条件” 或 “满足所有条件” 。但是这个东西显然不符合我们所熟知的经典容斥模型 ，我们仍然可以使用容斥计算它吗 ?

仍然可以

s = \sum_{i=0}^k h(i) \cdot g(i)

只不过我们不能无脑地套用 (-1)^i 的容斥系数，而是变成了未知的 h(i) ，我们要小心地求解这个容斥系数 。

在分析容斥系数时，我们应该围绕着这些核心对象

在这个问题中，我们要求所有的 “恰好 d 个二元环” 的方案数都只被计算 1 次。

如果我们按照原先不考虑二元环的方法进行计数，即 g(0) ，根据上面我们给出的 g 与 f 之间的关系式，我们得到。

g(0) = \sum_{i=0}^k \binom{i}{0} 2^{i} f(i)

我们发现对于每个恰好的方案 f(d) 被计算了 2^d 次 。

我们又希望

s = \sum_{i=0}^k f(i)

所以每个 f(d) 被多计算了 2^d - 1 次 。

列表如下

恰好 d 个二元环 1 2 3 4 5
实际算了 2 4 8 16 32
期望 1 1 1 1 1
多算了 1 3 7 15 31

我们逐项考虑容斥系数 h(i) 。

对于 h(0) 我们显然应该令其为 1 。

对于 h(1) ，为了使 f(1) 只被算 1 次，我们令 h(1) = -1

恰好 d 个二元环 1 2 3 4
g(0)贡献 2 4 8 16
g(1)贡献 -1 -4 -12 -32
最终 1 0 -4 -16

然后我们发现 f(2) 的次数归零了，我们要让它变回 1 ，则令 h(2)=1

恰好 d 个二元环 1 2 3 4
g(0)贡献 2 4 8 16
g(1)贡献 -1 -4 -12 -32
g(2)贡献 0 1 6 24
最终 1 1 2 8

然后令 h(3)=-1

恰好 d 个二元环 1 2 3 4
g(0)贡献 2 4 8 16
g(1)贡献 -1 -4 -12 -32
g(2)贡献 0 1 6 24
g(3)贡献 0 0 -1 -8
最终 1 1 1 0

然后令 h(4)=1

恰好 d 个二元环 1 2 3 4
g(0)贡献 2 4 8 16
g(1)贡献 -1 -4 -12 -32
g(2)贡献 0 1 6 24
g(3)贡献 0 0 -1 -8
g(4)贡献 0 0 0 1
最终 1 1 1 1

我们递归地求下去，可以发现 h(i)=(-1)^i

最终得到

\begin{aligned} s&=\sum_{i=0}^k h(i) \cdot g(i)\\ &=\sum_{i=0}^k (-1)^i \binom{k}{i} 2^{x-i}(x-i)! \end{aligned}

再乘上普通环部分的答案 2^y 输出即可 。

不止容斥

不过除了容斥，我们还可以有其他办法。

g(d)=\sum_{i=d}^k \binom{i}{d} 2^{i-d} f(i)

有点类似于二项式反演的基本形式，但是多了一个很丑陋的 2^{i-d} 的系数 。

但是它依然可以通过一些处理，应用二项式反演 ！

变形得到

2^d g(d) = \sum_{i=d}^k \binom{i}{d} 2^{i} f(i)

令

G(d) = 2^d \cdot g(d) F(d) = 2^d \cdot f(d)

则有

G(d) = \sum_{i=d}^k \binom{i}{d} F(i)

这样我们可以对 G 和 F 进行二项式反演 。

进行二项式反演

F(d)=\sum_{i=d}^k (-1)^{i-d} \binom{i}{d}G(i)

将 G 和 F 进行代换

f(d)=\sum_{i=d}^k (-2)^{i-d} \binom{i}{d}g(i)

将 f 直接带入答案

s=\sum_{i=0}^k f(i)

得到

s=\sum_{i=0}^k \sum_{j=i}^k (-2)^{j-i} \binom{j}{i} g(j)

经典的交换求和次序得到

s=\sum_{j=0}^k g(j) \sum_{i=0}^j (-2)^{j-i} \binom{j}{i}

我们发现内部求和就是经典的二项式展开

s=\sum_{j=0}^k g(j) (1-2)^{j}

然后我们就得到了和上面一样的东西

s=\sum_{i=0}^k (-1)^i g(i)

总答案是

终于写完了...

代码

核心代码如下，完整代码请自行访问剪贴板 或 提交记录

mint fc[N], fcv[N], inv[N], pw2[N];
mint binom(int n, int m) { return fc[n] * fcv[n - m] * fcv[m]; }

struct E {
    int u, v, vis;
    int get(int x) { return u ^ v ^ x; }
} e[N];

int n, p[N];
ve(int) g[N];
bool vis[N];
int tim, cnt;
int ring, ring2, chain;

int deg[N];
void dfs(int u, int fa, int &tp) {
    ++cnt, vis[u] = 1;
    for (int ei : g[u]) {
        if (e[ei].vis) { continue; }
        e[ei].vis = 1;
        int v = e[ei].get(u);
        if (v == fa) {
            tp = 1;
            deg[v]--, deg[u]--;
        } else {
            if (vis[v]) {
                tp = 2;
            } else {
                dfs(v, u, tp);
            }
        }
    }
}

void task() {
    n = rd();

    L(i, 1, n) {
        int x = rd();
        p[i] = x;
        e[i] = {i, x, 0};
        g[i].push_back(i), g[x].push_back(i);
    }
    L(i, 1, n) { deg[i] = siz(g[i]); }
    L(i, 1, n) {
        if (!vis[i]) {
            ++tim, cnt = 0;
            int tp = 0;
            dfs(i, 0, tp);
            if (tp == 1) {
                chain++, ring2 += (cnt == 2);
            } else {
                ring += (cnt > 1);
            }
        }
    }
    L(i, 1, n) {
        if (deg[i] > 2) { return wr("0\n"), void(); }
    }

    mint ans(0);
    L(i, 0, ring2) {
        ans += mint(neg1(i & 1)) * binom(ring2, i) * fc[chain - i] *
               pw2[chain - i];
    }
    ans *= pw2[ring];
    wr("%lld\n", ans.v);
}

鸣谢

E.Space.

Flying_Without_Wings

本题第一篇题解