本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-01-09 19:36:45

传送门：G - Only Once

题意：

给定 $n$，对于一个长度为 $n$，值域为 $n$ 的序列 $A$，我们按如下方法构造无限序列 $B_i(1 \le i \le n)$：

• $B_{i,1} = i$
• $B_{i,j} = A_{B_{i,j-1}}(j > 1)$

记 $S_i$ 为 $B_i$ 中只出现了一次的元素的个数，定义序列 $A$ 的价值为 $\sum_{i=1}^n S_i$，现在请求出所有 $n^n$ 个可能的序列 $A$ 的价值之和对 $M$ 取模的结果。

$n \le 2 \times 10^5, 10^8 \le M \le 10^9$.

这是不同于官方题解的麻烦不知道多少倍的邪道解法。

对于任意 $1 \le i \le n$，我们从 $i$ 向 $A_i$ 连一条有向边，不难发现每个点有且仅有一条出边，整张图形成一个内向基环树森林（记为 $\mathcal{T}$）。

先来考虑怎样计算单个 $\mathcal{T}$ 的价值，观察序列 $B_i$ 的构造方式不难发现 $B_i$ 即为从点 $i$ 出发，沿着出边一直走下去经过的点形成的序列，$S_i$ 即为从点 $i$ 出发进入环之前经过的点的数量，$\sum_{i=1}^n S_i$ 就是每个不在环上的点被经过的次数，也即其子树大小，不妨简记为 $\sum_{i=1}^{n} siz_i$。

接下来就可以大力列式子了：

$$ \begin{aligned} &\sum_{\mathcal{T}}\sum_{i=1}^n siz_i \ = &\sum_{\mathcal{T}}\sum_{i=1}^n i\sum_{j=1}^{n} [siz_j=i] \ = &\sum_{i=1}^n i \sum_{\mathcal{T}}\sum_{j=1}^{n} [siz_j=i] \ = &\sum_{i=1}^n i \binom{n}{i} i^{i-1} (n-i)^{n-i+1} \end{aligned} $$

解释一下最后一步，$\binom{n}{i}$ 为选出来组成这个大小为 $i$ 的子树的点的方案数，$i^{i-1}$ 为该树的形态数，即为 $i$ 个点的有标号有根树的数量（证明见Prufer 序列），而剩下的点加上根节点这总共 $n-i+1$ 个点每个点都能向剩下的 $n-i$ 个点随意连边，所以最后要乘上 $(n-i)^{n-i+1}$。

如果模数是个大质数，那么这题已经做完了，但关键是模数可能为合数，导致 $n!$ 的逆元不存在，从而没法求 $\binom{n}{i}$。解决办法是借鉴扩展卢卡斯定理的思想，考虑将模数质因数分解成 $\sum p_i^{k_i}$，单独求出在模 $p_i^{k_i}$ 意义下的答案，最后使用中国剩余定理合并出答案，简单说一下如何在模 $p^k$ 意义下求 $\binom{n}{m}$：

$$ \begin{aligned} &\binom{n}{m} \ = &\dfrac{n!}{m!(n-m)!} \ = &\dfrac{\dfrac{n!}{p^x}}{\dfrac{m!}{p^y} \dfrac{(n-m)!}{p^z}} p^{x-y-z} \end{aligned} $$

其中 $x$ 是最大的满足 $p^x | n!$ 的整数，$y,z$ 同理，其实就是将分子和分母中的质因数 $p$ 单独拿出来算，这样分母就和模数互质，可以求逆元了，我们可以直接在 $O(n)$ 的时间内预处理出来 $\dfrac{i!}{p^{x_i}}(1 \le i \le n)$，总复杂度即为 $O(nt + n \log n)$，其中 $t$ 为模数的不同的质因数的数量，最大为 $9$，这不和官方做法复杂度一样吗。

代码：

\/\/邪道解法
#include <bits\/stdc++.h>
#define lowbit(x) (x & -x)
#define eb emplace_back
#define pb push_back
#define mp make_pair
using namespace std;

typedef long long ll;
const int N = 2e5+5;

int n, M, cnt, ans;
int num[10][N];
ll fac[10][N], ifac[10][N], ppow[10][101], c[10], tmp[N];

pair<int, int> fctr[10];

inline int qpow(int a, int b, int Mod) {
    ll base = a, ans = 1;
    while (b) {
        if (b & 1) ans = ans * base % Mod;
        base = base * base % Mod;
        b >>= 1;
    }
    return ans;
}

void init() {
    int t = M;
    for (int i = 2; i * i <= t; i++) if (t % i == 0) {
        fctr[++cnt] = mp(i, 1);
        ppow[cnt][0] = 1;
        int tt = 0;
        while (t % i == 0) ppow[cnt][++tt] = (fctr[cnt].second *= i), t \/= i;
    }
    if (t != 1) fctr[++cnt] = mp(t, t), ppow[cnt][0] = 1;

    for (int i = 1; i <= cnt; i++) {
        auto [p, pw] = fctr[i];
        c[i] = M \/ pw * qpow(M \/ pw, pw \/ p * (p - 1) - 1, pw);

        fac[i][0] = 1;
        for (int j = 1; j <= n; j++) {
            tmp[j] = (j % p ? j : tmp[j \/ p]);
            fac[i][j] = fac[i][j - 1] * tmp[j] % pw;
            num[i][j] = num[i][j \/ p] + j \/ p;
        }

        ifac[i][n] = qpow(fac[i][n], pw \/ p * (p - 1) - 1, pw);
        for (int j = n; j; j--) ifac[i][j - 1] = ifac[i][j] * tmp[j] % pw;
    }
}

ll C(int n, int m) {
    ll ret = 0;
    for (int i = 1; i <= cnt; i++) {
        int pw = fctr[i].second;
        ll a = fac[i][n] * ifac[i][m] % pw * ifac[i][n - m] % pw * ppow[i][min(num[i][n] - num[i][m] - num[i][n - m], 100)] % pw;
        ret = (ret + c[i] * a) % M;
    }
    return ret;
}

int main() {
    scanf("%d%d", &n, &M);

    init();

    for (int i = 1; i < n; i++) ans = (ans + C(n, i) * qpow(i, i, M) % M * qpow(n - i, n - i + 1, M)) % M;

    printf("%d", ans);
    return 0;
}