「CMOI R1」Nilpotent 题解

· · 题解

首先，注意到矩阵的所有元素非负，因此某个元素是 1 还是 2 对矩阵 A 的 f(A) 值并没有影响。故不妨将所有大于等于 1 的元素视为 1。也即对于矩阵的每个元素，有 1 种可能为 0，另外 a-1 种可能为 1。

然后利用矩阵乘法和有向图的关系。0-1 矩阵 A 幂零，等价于由它构建的有向图是个 DAG（构建规则为：若 a_{ij}=1，则连接 i\rightarrow j 的有向边）。并且 f(A) 就等于这个 DAG 的最长链上的点的数量。

综上，我们将问题转化为：对于有向无环图 G，记其边的数量为 e(G)，其最长链上点个数为 l(G)，试求：

\sum _G l(G)(a-1)^{e(G)}

（其中 \sum_G 对所有 n 个点的 DAG 求和）

对于有向无环图 G，我们考虑如何求其最长链。最简单的方法就是令出度为 0 的节点深度为 1，然后对于每个点，令其深度为它所指的节点的深度的最大值 +\,1。那么，所有节点深度的最大值就是 l(G)。受此启发，我们设 G 深度为 i 的点有 a_i 个，则有：

\sum_{k=1}^{l(G)}a_k=n

且 \forall 1\le i\le l(G),a_i\neq 0。

枚举 l(G), a_1,\cdots,a_{l(G)}，我们考虑这样的 G 有几个。

首先，深度为 i+1 的点必须有一条边连向某个深度为 i 的点。然后，深度为 i+1 的点可以往深度低于 i 的点任意地连边。于是满足条件的 DAG 有这么多个：

\binom{n}{a_1,\cdots,a_{l(G)}}\prod_{i}\left(2^{a_{i}}-1\right)^{a_{i+1}}2^{a_{i+1}(a_1+\cdots+a_{i-1})}

但是这样就没有 e(G) 什么事了！因此，我们用 x 的次数来记录有向边条数，则上式应改写为：

\binom{n}{a_1,\cdots,a_{l(G)}}\prod_{i}\left[(1+x)^{a_{i}}-1\right]^{a_{i+1}}(1+x)^{a_{i+1}(a_1+\cdots+a_{i-1})}

故而我们有：

\sum _ G l(G)x^{e(G)}=\sum_{a_1+\cdots+a_k=n, a_k\neq 0}k\binom{n}{a_1,\cdots,a_k}\prod_{i}\left[(1+x)^{a_{i}}-1\right]^{a_{i+1}}(1+x)^{a_{i+1}(a_1+\cdots+a_{i-1})}

令 x=a-1 得答案为：

n!\sum_{a_1+\cdots+a_k=n, a_k\neq 0}k\prod_{i}\dfrac{\left(a^{a_{i}}-1\right)^{a_{i+1}}}{a_i!}a^{a_{i+1}(a_1+\cdots+a_{i-1})}

直接计算可以通过前三个 Subtask。

下面考虑用 DP 优化计算。设 f_{k,s,l} 为：

\begin{aligned}f_{k,s,l}&=\sum_{a_1+\cdots+a_k=s,a_k=l}\prod_{i}\dfrac{\left(a^{a_{i}}-1\right)^{a_{i+1}}}{a_i!}a^{a_{i+1}(a_1+\cdots+a_{i-1})}\end{aligned}

则答案为 n!\sum _ {k,l}k f_ {k,n,l}。

枚举 r=a_{k-1}，可知递推式如下：

f_{k,s,l}=\sum_{r} f_{k-1,s-l,r}\dfrac{\left(a^{r}-1\right)^{l}}{l!}a^{l(s-l-r)}

且边界为 f_{1,s,l}=[s=l]\frac{1}{s!}。

这样就是一个 \Theta(n^4) 或 \Theta(n^4\log n) 的 DP，能过前四个 Subtask。

我们继续考虑优化，注意到递推式中，s,l 都和求和指标 r 有关，唯独 k 和 r 没什么关系，这引导我们设：

g_{s,l}=\sum_k f_{k,s,l}

但是这样的话答案就算不了了，所以我们再设：

h_{s,l}=\sum_k kf_{k,s,l}

这样答案就是 n!\sum _ l h_{n,l}。接着我们考虑写出 g,h 的状态转移方程。

\begin{aligned}g_{s,l}&=\sum_{k,r} f_{k-1,s-l,r}\dfrac{\left(a^{r}-1\right)^{l}}{l!}a^{l(s-l-r)}\\&=\sum_{r}g_{s-l,r}\dfrac{\left(a^{r}-1\right)^{l}}{l!}a^{l(s-l-r)}\end{aligned}

而 h 的方程是类似的：

\begin{aligned}h_{s,l}&=\sum_{k,r} kf_{k-1,s-l,r}\dfrac{\left(a^{r}-1\right)^{l}}{l!}a^{l(s-l-r)}\\&=\sum_{k,r} (k-1)f_{k-1,s-l,r}\dfrac{\left(a^{r}-1\right)^{l}}{l!}a^{l(s-l-r)}+g_{s,l}\\&=\sum_{r}h_{s-l,r}\dfrac{\left(a^{r}-1\right)^{l}}{l!}a^{l(s-l-r)}+g_{s,l}\end{aligned}

边界条件是 g_{k,k}=h_{k,k}=\frac 1{k!}。

预处理 a 相关的快速幂，可得一个 \Theta(n^3) 的做法，足以通过此题。

核心代码如下：

int Solve(){
    Frac[0] = PA[0] = 1;
    for(int i = 1; i < Mx; ++i) Frac[i] = 1ll * i * Frac[i - 1] % Mod;
    Infs[Mx - 1] = FastPow(Frac[Mx - 1], Nod - 1);
    for(int i = Mx - 1; i; --i) Infs[i - 1] = 1ll * i * Infs[i] % Mod;
    for(int i = 0; i < Mx; ++i) for(int j = 0; j < Mx; ++j) U[i][j] = FastPow(FastPow(a, i) - 1, j);
    for(int i = 1; i < Nx; ++i) PA[i] = 1ll * PA[i - 1] * a % Mod;

    for(int s = 0; s <= n; ++s){
        G[s][s] = H[s][s] = Infs[s];
        for(int l = 1; l < s; ++l){
            ll Q = 0, Q2 = 0;
            for(int r = 1; r <= s - l; ++r){
                Q += 1ll * G[s - l][r] * PA[(s - l - r) * l] % Mod * U[r][l] % Mod;
                Q2 += 1ll * H[s - l][r] * PA[(s - l - r) * l] % Mod * U[r][l] % Mod;
            }
            G[s][l] = Q % Mod * Infs[l] % Mod;
            H[s][l] = (Q2 % Mod * Infs[l] + G[s][l]) % Mod;
        }
    }

    ll Ans = 0;
    for(int s = 1; s <= n; ++s) Ans += H[n][s];
    Ans = Ans % Mod * Frac[n] % Mod;

    return Ans < 0 ? Ans + Mod : Ans;
}

闲话：

比赛开始时我先看了 G 题，虽然一眼数树，但是根本不会组合推导，所以果断写 F 题。因为模数非质数，我就想着对两个质数分别求答案，再暴力枚举答案（不想写 CRT）。因此我代码里的模数不是 const 类型，导致我就算写了 \Theta(n^3) 的正解仍旧 TLE。最后把代码复制成两份，一份用 Mod0，一份用 Mod1，然后就过了。有点可惜，是二杀，鉴定为不会数学导致的。