题解 - Aizu 2993 Invariant Tree

非常好 Prufer 序列数数，爱了。

简述题意

给定排列 $p$，求有多少棵点为 $1\sim n$ 的无根树，满足对于任意一条边 $x\to y$，边 $p_x\to p_y$ 存在。模 $998244353$。$n\le 5\times 10^5$。

分析

这题感觉没部分分做不了。

从置换环发掘性质

部分分剑指一元环和二元环，启发我们从排列的置换环角度考虑（虽然好像没部分分也会想到？）。只有一元环，就是 Prufer 序列结论。只有二元环，打表发现结论是 $n^{\frac{n}{2}-1}$，如何理解呢？两个二元环合并，比如 $(a,b)$ 和 $(c,d)$，有两种方式：$a\to c,b\to d$ 或 $a\to d, b\to c$，每个二元环左右两种情况共 $2^{\frac{n}{2}-1}$，形成无根树方案数为 $(\frac{n}{2})^{\frac{n}{2}-2}$，最后要形成一棵树，要再连一条边，只能选择一个二元环连，那就是 $\frac{n}{2}$，乘起来就是结论了。

所以我们可以想想如何刻画两个环合并的过程。发现条件是两个环大小有因倍关系（否则边数过大），不妨假设 $a|b$，则连的边数为 $b$，方案数为 $a$。此后不可以有大小小于 $b$ 的环与 $b$ 相连，否则边数也是过大。所以一个大小 $>2$ 的环可以向同大小合并，可以向比它小的合并，此后就可以将它删去。

假设我们做了很多操作，最后没有一元环和二元环，可以发现答案为 $0$。因为一个大小 $>2$ 的环内部不能连边，一旦有连边就会成环。

那我们对整个算法就有一个雏形：对于 $>2$ 的环，每个大小做计算，然后乘到答案去；对于一元环和二元环最终判断。

只有一元环和二元环

我们已有的结论是：两者都没有，答案为 $0$；只有一元环，答案为 $n^{n-2}$；只有二元环，答案为 $n^{\frac{n}{2}-1}$。

打表发现，两种都有的时候，假设有 $c_1$ 个一元环，$c_2$ 个二元环（$c_1+2c_2=n$），则答案为 $c_1^{c_1-1}n^{c_2-1}$。可以用下方神秘 Lemma 证明。

大于 2 的环

考虑大小为 $i$ 的环，假设有 $c_i$ 个，它们应该是自己形成了若干棵有根树，然后往因数合并。假设有 $j$ 棵有根树，那么总贡献是：

$$\textrm{方案数}\times i^{c_i-j}(\sum_{d|i\land d<i}c_d)^j$$

括号内可以调和级数预处理（事实上由于不同的环大小只有 $O(\sqrt n)$ 种，所以可以 $O((\sqrt n)^2)$ 做），枚举 $j$，那么只需要求$n$ 个点划分成 $m$ 棵有根树的方案数。有以下的两条路可走（都是我想不出来的）：

神秘 Lemma

方案数为 $\binom{n-1}{m-1}n^{n-m}$。（这里已经考虑了所有根的组合。）

证明：我们设一个虚点 $0$，让所有的根与它相连，则 $0$ 的度数被钦定为 $m$，也就是它在 Prufer 序列中出现了 $m-1$ 次（另外一个儿子就是最后剩下来的另一个点），这样的序列的个数为 $\binom{n-1}{m-1}n^{n-m}$（注意 Prufer 序列总长为 $n-1$，因为增加了点）。

那就做完了。把这个式子直接带入只有一元环和二元环的情景，用二项式定理化简就得到结论。

活用 Prufer 序列

膜拜传奇大师 qwqUwU。

我们不枚举根的数目，直接算总贡献。沿用虚点的思想，算 Prufer 序列每一位的贡献。若这一位是 $0$，有 $\sum_{d|i\land d<i}c_d$ 的贡献，令它为 $e_i$；否则有 $i$ 的贡献。然后做序列带权计数，每一步从 $c_i+1$ 种选择变为 $c_i$ 种 $i$ 的贡献或 $1$ 种 $e_i$ 的贡献，总贡献就是 $(e_i+ic_i)^{c_i-1}$。最后一条树边要再乘一遍与 $0$ 相连的 $e_i$ 贡献。

代码

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

int read() {
  int x(0), c(getchar());
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + (c - '0'), c = getchar();
  return x;
}
void write(int x) {
  static char buf[14];
  if (!x) {
    putchar('0');
    return;
  }
  int d(0);
  while (x) buf[d++] = x % 10 + '0', x /= 10;
  while (d) putchar(buf[--d]);
}

const int MXN = 500005;
const int DVS = 998244353;
int T, N, prm[MXN], ans, cnt[MXN], coe[MXN];
bool vis[MXN];

int main() {
  T = read();
  while (T--) {
    N = read();
    for (int i(0); i != N; ++i) prm[i] = read() - 1;
    for (int i(0); i <= N; ++i) vis[i] = 0, cnt[i] = 0, coe[i] = 0;
    for (int i(0); i != N; ++i) {
      if (!vis[i]) {
        int j(i), len(0);
        while (!vis[j]) {
          vis[j] = true;
          ++len;
          j = prm[j];
        }
        ++cnt[len];
      }
    }
    for (int i(1); i <= N; ++i)
      if (cnt[i])
        for (int j(i + i); j <= N; j += i) coe[j] += i * cnt[i];
    ans = 1;
    for (int i(3); i <= N; ++i) {
      if (!cnt[i]) continue;
      int bas((coe[i] + cnt[i] * 1LL * i) % DVS);
      ans = ans * 1LL * coe[i] % DVS;
      for (int j(0); j != cnt[i] - 1; ++j) ans = ans * 1LL * bas % DVS;
    }
    int c1(cnt[1]), c2(cnt[2]);
    int n(c1 + c2 * 2);
    if (!c1 && !c2) {
      ans = 0;
    } else if (!c1) {
      for (int i(0); i != c2 - 1; ++i) ans = ans * 1LL * n % DVS;
    } else if (!c2) {
      if (c1 > 1)
        for (int i(0); i != n - 2; ++i) ans = ans * 1LL * n % DVS;
    } else {
      for (int i(0); i != c1 - 1; ++i) ans = ans * 1LL * c1 % DVS;
      for (int i(0); i != c2 - 1; ++i) ans = ans * 1LL * n % DVS;
    }
    write(ans), putchar('\n');
  }
  return 0;
}