题解：AT_codefestival_2016_final_f Road of the King

_zuoqingyuan · 2025-12-13 14:00:47 · 题解

啊呀。

我们考虑一下对这个东西计数，要维护是什么抽象的东西。

先假设当前走了 i 步，则可以维护一个以 1 所在的 scc 为起点，由很多 scc 连接构成的一条有向链。

红点就是 1 号点的所在的 scc，蓝点就是当前其他的 scc。我们最后要求走完 m 步只剩下一个红点的方案数。

注意到我们实际走到哪个节点时无意义的，所以不需要记录这个东西。考虑接下来第 i+1 步怎么走。

• 首先可能走到一个新的点，得到一个新的 scc。

这个黄点可以选择的方案数是 n-s，其中 s 是目前的链（不包括黄点）的点数之和。可以维护 s 来转移。

• 其次可能走到一个之前走过的点，先考虑特殊的，我们走到了 1 所在的 scc 内的一个点，此时我们走到的所有点都会缩成一个 scc。

这一步可以走的方案数是 1 所在 scc 内的点数，可以考虑维护。

• 最后，是走到一个没走到的点的其他情况，我们把一些蓝色点缩成了一个 scc。

这一步以走的方案数是蓝色点 scc 内的点数之和，不难发现我们并不关注每个蓝色 scc 点内的具体点数，只关心和。

整合思路，设 f_{i,j,k} 表示当前走了 i 步，蓝色 scc 内点数之和为 j，红色 scc 内点数为 k 的方案数。当前的总点数就是 (j+k)。

第一种转移，其实是新增加了一个蓝点：

第二种转移，实际上是将一堆蓝色点变成一个蓝色点，蓝色点的总点数是不变的：

第三种转移，将所有的蓝色点变成一个红色点了，转移即可：

不难发现确定状态后，状态的转移是 O(1) 的。而状态数是 O(n^3) 的，所以时间复杂度为 O(n^3)。

#include <iostream>
#include <cstdio>
using namespace std;
const int N=305;
const int mod=1e9+7;
typedef long long ll;
int n,m;
ll f[N][N][N];
int main(){
    cin>>n>>m;
    f[0][0][1]=1;
    for(int i=0;i<m;i++){
        for(int j=0;j<=n;j++){
            for(int k=0;k<=n-j;k++){
                if(!f[i][j][k])continue;
                f[i+1][j+1][k]+=f[i][j][k]*(n-j-k)%mod;
                f[i+1][j+1][k]%=mod;
                f[i+1][j][k]+=f[i][j][k]*j%mod;
                f[i+1][j][k]%=mod;
                f[i+1][0][j+k]+=f[i][j][k]*k%mod;
                f[i+1][0][j+k]%=mod;
            }
        }
    }
    cout<<f[m][0][n]<<endl;
    return 0;
} 

如有错误，请指出。