自动搬运

查看原文

来自洛谷，原作者为

	Petit_Souris 鼓励的话语 无论多少次我都会说给你听 | 你在名为弱小的深渊 究竟看见过什么 | 天空中出现了一种罕见的天文现象

搬运于2025-08-24 23:04:55，当前版本为作者最后更新于2024-10-10 11:11:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

We Want To Run 是神曲，出题人有品啊！

真不是蓝题嘛（？）

$a$ 是多少不是很重要，我们只关心每个位置是否是 $0$。

首先很容易想到用一个经典的图论模型来刻画矩阵的幂：若 $A_{i,j}>0$，那么从 $i$ 向 $j$ 连一条边，此时 $(A^k)_{i,j}$ 就表示 $i\to j$ 是否存在长度为 $k$ 的路径。

那么题目中的 $f(A)$ 实际上就是最小的 $b$ 满足图上不存在长度为 $b$ 的路径。显然当图上有环的时候不存在合法的 $b$，而当图为 DAG 时 $b$ 就是图上最长路径的点数。

最长路径启发我们把图按照从该点出发的最长路分层，设分成了 $S_1,S_2,\dots S_{d}$ 这些点集，那么 $\forall i\ge 2,x\in S_i$，都需要满足 $x$ 向 $S_{i-1}$ 中至少一个点连边，且不存在 $x\in S_i,y\in S_j,i\le j$，$x$ 向 $y$ 连边。

根据这个性质，我们可以设计一个 dp，每次剥掉所有最下面一层的点（这其实很类似 DAG 计数对 $0$ 度点容斥的思想）。设 $dp_{i,j,k}$ 表示 $i$ 层点，用了 $j$ 个点，上一层有 $k$ 个点的方案数。

转移枚举这层放了 $p$ 个点，$dp_{i,j,k}\times \binom{j+p}{p}(a^k-1)^pa^{p(j-k)}\to dp_{i+1,j+p,p}$（其中第一个 $(a^k-1)^p$ 表示相邻层的连边方案，$a^{p(j-k)}$ 表示往 $i-1$ 层及以前的连边方案）。答案为 $\sum\limits_{i=1}^{n}i\sum\limits_{k=1}^{n}dp_{i,n,k}$。时间复杂度 $\mathcal O(n^4)$，期望得分 70。

考虑优化这个东西。观察到我们的转移系数和 $i$ 根本无关，这个 $i$ 只是用来最后统计答案的时候乘上一个 $i$ 的系数。于是想到用组合意义拆掉这个 $i$，转化成在 $i$ 层中选择一层作为关键层的方案数。这样我们的 dp 就不需要记录 $i$ 了，状态变为 $dp_{j,k,0/1}$ 表示 $j$ 个点，上一层有 $k$ 个点，是否已经选出了关键层的方案数。转移分类讨论一下这层是否选做关键层，时间复杂度 $\mathcal O(n^3)$，可以通过。

观察到过程中没有需要求逆元的地方，所以其实可以任意模数来着，不知道出题人给了个特别的模数是想 CRT 还是啥意思，不太懂。

实现的时候注意读入的 $a$ 的范围是 unsigned long long 的。

#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
ull read(){
    ull x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}
    return x;
}
void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const ll N=609,Mod=202407031;
ll n,A,pwA[N*N],pwq[N][N],C[N][N],dp[N][N][2],cur;
ll pw(ll x,ll p){
    ll res=1;
    while(p){
        if(p&1)res=res*x%Mod;
        x=x*x%Mod,p>>=1;
    }
    return res;
}
bool Med;
int main(){
    cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
    n=read(),A=read()%Mod;
    pwA[0]=1;
    rep(i,1,n*n)pwA[i]=pwA[i-1]*A%Mod;
    rep(i,1,n){
        pwq[i][0]=1;
        rep(j,1,n)pwq[i][j]=pwq[i][j-1]*(pwA[i]-1+Mod)%Mod;
    }
    rep(i,0,n){
        C[i][0]=1;
        rep(j,1,i)C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mod;
    }
    ll ans=0;
    rep(i,1,n)dp[i][i][0]=dp[i][i][1]=1;
    rep(j,1,n){
        rep(k,1,n){
            rep(o,0,1){
                ll v=dp[j][k][o];
                if(!v)continue;
                rep(p,1,n-j){
                    dp[j+p][p][o]=(dp[j+p][p][o]+
                    v*pwq[k][p]%Mod*pwA[p*(j-k)]%Mod*C[j+p][p])%Mod;
                    if(!o)dp[j+p][p][1]=(dp[j+p][p][1]+
                    v*pwq[k][p]%Mod*pwA[p*(j-k)]%Mod*C[j+p][p])%Mod;
                }
            }
        }
    }
    rep(k,1,n)ans=(ans+dp[n][k][1])%Mod;
    write(ans);
    cerr<<"\n"<<clock()*1.0/CLOCKS_PER_SEC*1000<<"ms\n";
    return 0;
}