题解：P11173 「CMOI R1」We Want To Run / Nilpotent

· · 题解

节选自：DP做题记录（三）（2025.4.5 - 2025.4.19）

安利一下我的博客

套用非常经典的线性代数结论，一张图的邻接矩阵的 k 次方后每个位置 A_{u, v} 就表示 u 到 v 的所有路径中长度为 k 的路径条数。

注意到这张图中左右边权非负，那么在矩乘时，如果两个位置都不为 0，那么乘积也不为 0，必须至少有一个是 0 才可以，于是，每个位置 A_{i, j} 我们不用考虑它的具体取值，只用考虑它是否为 0。

那么现在，A^b = O 的含义就变成了对一个边权只有 0 和 1 的图，找到最小的 b 使得图中没有长度为 b 的链。显然，如果这张图存在环，那么图中就不存在最长链（可以一直在环上绕），因此这张图一定是一个 DAG。

由于我们要统计方案数，因此我们考虑枚举贡献。如果这张图中最长链上的点数为 b，那么说明最长链的长度为 b - 1，于是对答案的贡献就是 b。由于是 DAG 我们可以按拓扑序一层一层枚举。

我们设 dp_{i, j, k} 表示前 i 个点分了 j 层，上一层有 k 个点的方案数。我们先枚举这一层的点数 p，那么这 p 个点就可以从这 i + p 个点中选出，因此转移时首先要乘以 \displaystyle\binom{i + p}{p}。

其次，这一层的点必须至少与上一层的 1 个点连边，边权任意，于是转移时又要乘以 (a^k - 1)^p（减 1 是因为不能一个点都不连）。

最后，这一层的点可以与之前层的点随便连边，之前的点一共有 i - k 个，于是答案又要乘以 a^{p(i - k)}，因此我们就得到了转移方程 dp_{i, j, k} \times \displaystyle\binom{i + p}{p} (a^k - 1)^p a^{p(i - k)} = dp_{i + p, j + 1, p}。那么答案就是 \displaystyle\sum_{j = 1}^n j \sum_{k = 1}^{n - j + 1} dp_{n, j, k}。

我们其实可以发现，j 其实顶没用的（和我一样），只是在最后求答案时要乘以 j。我们考虑 j 的组合意义，就是在这 j 层中选一层作为关键层。这是因为 \displaystyle\binom j1 = j。

现在我们可以改变 DP 的函数了，设 dp_{i, j, 0 / 1} 表示给前 i 个数分层，上一层有 j 个数，且是否选择过关键层的答案，dp_{i, j, 0} 到 dp_{i + p, p, 0}，dp_{i, j, 1} 到 dp_{i + p, p, 1} 直接用之前的转移方程。对于每一层，都可以选择这一层成为关键层，于是把 dp_{i, j, 0} 按照转移方程加到 dp_{i + p, p, 1} 就可以了，复杂度降低到 O(n^3)，足以通过此题。

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int N = 6e2 + 9, MOD = 202407031;
int dp[N][N][2], binom[N][N], pwr[N * N], po[N][N], n, a, ans;
int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') 
            f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        x = ((x << 1) + (x << 3) + (ch ^ 48));
        ch = getchar();
    }
    return x * f;
}
void write(int x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
signed main(){
    n = read();
    a = read();
    a %= MOD;
    pwr[0] = 1;
    for(int i = 1; i <= n * n; i++)
        pwr[i] = pwr[i - 1] * a % MOD;
    for(int i = 1; i <= n; i++){
        po[i][0] = 1;
        for(int j = 1; j <= n; j++)
            po[i][j] = po[i][j - 1] * (pwr[i] - 1 + MOD) % MOD;
    }
    binom[0][0] = 1;
    for(int i = 1; i <= n; i++){
        binom[i][0] = 1;
        for(int j = 1; j <= i; j++)
            binom[i][j] = (binom[i - 1][j] + binom[i - 1][j - 1]) % MOD;
    }
    for(int i = 1; i <= n; i++)
        dp[i][i][1] = dp[i][i][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(dp[i][j][0] != 0){
                for(int p = 1; p <= n - i; p++){
                    dp[i + p][p][0] = (dp[i + p][p][0] + dp[i][j][0] * binom[i + p][p] % MOD * po[j][p] % MOD * pwr[p * (i - j)] % MOD) % MOD;
                    dp[i + p][p][1] = (dp[i + p][p][1] + dp[i][j][0] * binom[i + p][p] % MOD * po[j][p] % MOD * pwr[p * (i - j)] % MOD) % MOD;
                }
            }
            if(dp[i][j][1] != 0){
                for(int p = 1; p <= n - i; p++)
                    dp[i + p][p][1] = (dp[i + p][p][1] + dp[i][j][1] * binom[i + p][p] % MOD * po[j][p] % MOD * pwr[p * (i - j)] % MOD) % MOD;
            }   
        }
    }
    for(int i = 1; i <= n; i++)
        ans = (ans + dp[n][i][1]) % MOD;
    write(ans);
    return 0;
}