专栏文章

Fate

DDangerise
P11563题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@min42b6g
此快照首次捕获于
2025/12/01 20:14
3 个月前
此快照最后确认于
2025/12/01 20:14
3 个月前
查看原文
P11563 【MX-X7-T4】[LSOT-3] 命运

题意

给定一个长度为 nn 的序列 p1,…,pnp_1, \ldots, p_n（未必为排列），保证 1≤pi≤n1 \le p_i \le n。求满足以下条件的排列 a1,…,ana_1, \ldots, a_n 的个数，对 998244353998244353 取模：
对每个 1≤i≤n1 \le i \le n，都有 ai=pia_i=p_i 或者 api=ia_{p_i}=i 成立。

分析

评价为比较综合和复杂的计数题，难度不止蓝，没有做出来。由于笔者做了很久，所以这篇题解会比较废话。
虽然题目描述很抽象，完全不懂在说什么，但是可以明显看出来一定的图论倾向 。
会被第 ii 个事件影响的是第 aia_i 个事件
经历了第 ii 个事件后影响了事件 pip_i
我们将 pip_i 和 aia_i 看作是点 ii 的一条边，我们可以将序列 pp 和 aa 分别转化成基环树森林 。
记 pp 得到基环树森林 PP ， aa 得到 AA 。
对每个 1≤i≤n1 \le i \le n，都有 ai=pia_i = p_i 或者 api=ia_{p_i} = i 成立 。
我们分析这个条件在 PP 和 AA 之间建立了何种联系 。
对于 PP 中的一条边 i→pii \to p_i ，AA 中需要存在一条边 i→pii \to p_i 或者 pi→ip_i \to i 。
也就是说 PP 中的方向并不重要，我们将 PP 当作无向图处理， 但是 AA 还需要是有向图，毕竟我们要对 aa 计数，不能舍弃原排列 aa 中带来的方向信息 。
注意到 aa 是一个排列，可以推导得到对于 AA 中的任意一点 uu ，uu 的入度至多为 11 ，出度至多为 11 。
由于 PP 的每条边都要在 AA 中对应，所以 PP 的每个点的度数也不能超过 22 ，否则无解。
而 PP 还是基环树森林，所以 PP 的每个联通块都是环 ？
并非如此，如果 PP 中出现了重边，由 pi=j,pj=ip_i = j, p_j = i 生成 i→j,j→ii \to j,j \to i ，这种情况下，由于我们将 PP 视作无向图，所以重边并不会导致实际上度数的增加。
所以 PP 的联通块除了环以外，还可以是一个链上带重边，或者说二元环。
如图所示
我们考虑对 PP 中的每一个联通块，对 AA 中的对应联通块进行计数。
先考虑 PP 中的环，它在 AA 中也必然是一个相应的环，但是 AA 是有向图，我们还要考虑边的方向。由于每个点只有一个出度和一个入度，所以整个环的方向是相同的，整体要么呈顺时针，要么呈逆时针。记 PP 中有个 yy 个环，它们会产生 2y2^y 的方案数。
然后是 PP 中的链，类似地，我们要对 AA 中的的链进行定向，但是注意到，一条链的头部缺乏一个出度，尾部缺乏一个入度。我们可以让头部自由地连向其他链的尾部，或者自己的尾部，让自己也变成一个环。
记 PP 中有 xx 个链，它们产生的方案数是 2x⋅x!2^x \cdot x! ，其中 2 的幂来自于不同方向，阶乘来自于链的不同拼接的方案数。

容斥

但是还没完，我们还遗漏了一个点 。
在 PP 中可能会出现如图的独立的二元环结构，由于我们认为 PP 是一个无向图，然后就会变成一个长度为 22 的链 。
在上述的计数过程中，如果这个长度为 22 的链，我们对其进行两次定向，然后发生了 “自交” ，就会产生
这其实是本质相同的一种方案，我们应想办法排除 。
以下我们来仔细地处理链的部分的方案数 。
我们记 f(d)f(d) 为恰好 dd 个二元环的情况下链的部分的答案的方案数 。
而链的部分的答案就是
s=∑i=0kf(i)s = \sum_{i=0}^k f(i)
通常而言，“恰好” 是不好计算的，而 “钦定” 是好计算的 。我们记 g(d)g(d) 为钦定 dd 个二元环的情况下链的部分的答案的方案数 ，也就是我们任意选取 dd 个长度为 2 的链 ，要求这 dd 条链自交，其余的链我们仍视作普通的链进行处理。
那么 gg 就很好计算了，容易得到
g(d)=(kd)2x−d(x−d)!g(d)=\binom{k}{d} 2^{x-d} (x-d)!
但是 “钦定” 和 “恰好” 是差得远的，当我们钦定 dd 个二元环时，实际上包含了很多 ≥d\ge d 的恰好的情况。
我们可以推得它们之间的关系是
g(d)=∑i=dk(id)2i−df(i)g(d)=\sum_{i=d}^k \binom{i}{d} 2^{i-d} f(i)
而如果我们不考虑二元环，也就是上文我们原先的算法，答案就是 g(0)g(0) 。
容斥的一个很重要的功能就是建立“钦定”与“恰好”之间的联系 ，我们考虑使用容斥。
一般来讲我们可以用容斥计算 “满足任意条件” 或 “满足所有条件” 。但是这个东西显然不符合我们所熟知的经典容斥模型 ，我们仍然可以使用容斥计算它吗 ?
仍然可以
s=∑i=0kh(i)⋅g(i)s = \sum_{i=0}^k h(i) \cdot g(i)
只不过我们不能无脑地套用 (−1)i(-1)^i 的容斥系数，而是变成了未知的 h(i)h(i) ，我们要小心地求解这个容斥系数 。
在分析容斥系数时，我们应该围绕着这些核心对象
  • 我要算什么
  • 我实际算了什么
  • 我多算了什么
在这个问题中，我们要求所有的 “恰好 dd 个二元环” 的方案数都只被计算 11 次。
如果我们按照原先不考虑二元环的方法进行计数，即 g(0)g(0) ，根据上面我们给出的 gg 与 ff 之间的关系式，我们得到。
g(0)=∑i=0k(i0)2if(i)g(0) = \sum_{i=0}^k \binom{i}{0} 2^{i} f(i)
我们发现对于每个恰好的方案 f(d)f(d) 被计算了 2d2^d 次 。
我们又希望
s=∑i=0kf(i)s = \sum_{i=0}^k f(i)
所以每个 f(d)f(d) 被多计算了 2d−12^d - 1 次 。
列表如下
恰好 d 个二元环12345
实际算了2481632
期望11111
多算了1371531
我们逐项考虑容斥系数 h(i)h(i) 。
对于 h(0)h(0) 我们显然应该令其为 11 。
对于 h(1)h(1) ，为了使 f(1)f(1) 只被算 11 次，我们令 h(1)=−1h(1) = -1
恰好 d 个二元环1234
g(0)贡献24816
g(1)贡献-1-4-12-32
最终10-4-16
然后我们发现 f(2)f(2) 的次数归零了，我们要让它变回 11 ，则令 h(2)=1h(2)=1
恰好 d 个二元环1234
g(0)贡献24816
g(1)贡献-1-4-12-32
g(2)贡献01624
最终1128
然后令 h(3)=−1h(3)=-1
恰好 d 个二元环1234
g(0)贡献24816
g(1)贡献-1-4-12-32
g(2)贡献01624
g(3)贡献00-1-8
最终1110
然后令 h(4)=1h(4)=1
恰好 d 个二元环1234
g(0)贡献24816
g(1)贡献-1-4-12-32
g(2)贡献01624
g(3)贡献00-1-8
g(4)贡献0001
最终1111
我们递归地求下去，可以发现 h(i)=(−1)ih(i)=(-1)^i
最终得到
s=∑i=0kh(i)⋅g(i)=∑i=0k(−1)i(ki)2x−i(x−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}
再乘上普通环部分的答案 2y2^y 输出即可 。

不止容斥

不过除了容斥，我们还可以有其他办法。
g(d)=∑i=dk(id)2i−df(i)g(d)=\sum_{i=d}^k \binom{i}{d} 2^{i-d} f(i)
有点类似于二项式反演的基本形式，但是多了一个很丑陋的 2i−d2^{i-d} 的系数 。
但是它依然可以通过一些处理，应用二项式反演 ！
变形得到
2dg(d)=∑i=dk(id)2if(i)2^d g(d) = \sum_{i=d}^k \binom{i}{d} 2^{i} f(i)
令
G(d)=2d⋅g(d)G(d) = 2^d \cdot g(d)
F(d)=2d⋅f(d)F(d) = 2^d \cdot f(d)
则有
G(d)=∑i=dk(id)F(i)G(d) = \sum_{i=d}^k \binom{i}{d} F(i)
这样我们可以对 GG 和 FF 进行二项式反演 。
进行二项式反演
F(d)=∑i=dk(−1)i−d(id)G(i)F(d)=\sum_{i=d}^k (-1)^{i-d} \binom{i}{d}G(i)
将 GG 和 FF 进行代换
f(d)=∑i=dk(−2)i−d(id)g(i)f(d)=\sum_{i=d}^k (-2)^{i-d} \binom{i}{d}g(i)
将 ff 直接带入答案
s=∑i=0kf(i)s=\sum_{i=0}^k f(i)
得到
s=∑i=0k∑j=ik(−2)j−i(ji)g(j)s=\sum_{i=0}^k \sum_{j=i}^k (-2)^{j-i} \binom{j}{i} g(j)
经典的交换求和次序得到
s=∑j=0kg(j)∑i=0j(−2)j−i(ji)s=\sum_{j=0}^k g(j) \sum_{i=0}^j (-2)^{j-i} \binom{j}{i}
我们发现内部求和就是经典的二项式展开
s=∑j=0kg(j)(1−2)js=\sum_{j=0}^k g(j) (1-2)^{j}
然后我们就得到了和上面一样的东西
s=∑i=0k(−1)ig(i)s=\sum_{i=0}^k (-1)^i g(i)
总答案是
终于写完了...

代码

核心代码如下，完整代码请自行访问剪贴板 或 提交记录
CPP
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
本题第一篇题解

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...