题解：P11173 「CMOI R1」We Want To Run / Nilpotent
Petit_Souris
·
·
题解
We Want To Run 是神曲，出题人有品啊！
真不是蓝题嘛（？）
首先很容易想到用一个经典的图论模型来刻画矩阵的幂：若 $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 的。
```cpp
#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;
}
```