专栏文章

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

oorange_new
P11173题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mipl16nh
此快照首次捕获于
2025/12/03 13:44
3 个月前
此快照最后确认于
2025/12/03 13:44
3 个月前
查看原文
节选自：DP做题记录（三）（2025.4.5 - 2025.4.19）
安利一下我的博客
套用非常经典的线性代数结论，一张图的邻接矩阵的 kk 次方后每个位置 Au,vA_{u, v} 就表示 uu 到 vv 的所有路径中长度为 kk 的路径条数。
注意到这张图中左右边权非负，那么在矩乘时，如果两个位置都不为 00，那么乘积也不为 00，必须至少有一个是 00 才可以，于是，每个位置 Ai,jA_{i, j} 我们不用考虑它的具体取值，只用考虑它是否为 00。
那么现在，Ab=OA^b = O 的含义就变成了对一个边权只有 00 和 11 的图，找到最小的 bb 使得图中没有长度为 bb 的链。显然，如果这张图存在环，那么图中就不存在最长链（可以一直在环上绕），因此这张图一定是一个 DAG。
由于我们要统计方案数，因此我们考虑枚举贡献。如果这张图中最长链上的点数为 bb，那么说明最长链的长度为 b−1b - 1，于是对答案的贡献就是 bb。由于是 DAG 我们可以按拓扑序一层一层枚举。
我们设 dpi,j,kdp_{i, j, k} 表示前 ii 个点分了 jj 层，上一层有 kk 个点的方案数。我们先枚举这一层的点数 pp，那么这 pp 个点就可以从这 i+pi + p 个点中选出，因此转移时首先要乘以 (i+pp)\displaystyle\binom{i + p}{p}。
其次，这一层的点必须至少与上一层的 11 个点连边，边权任意，于是转移时又要乘以 (ak−1)p(a^k - 1)^p（减 11 是因为不能一个点都不连）。
最后，这一层的点可以与之前层的点随便连边，之前的点一共有 i−ki - k 个，于是答案又要乘以 ap(i−k)a^{p(i - k)}，因此我们就得到了转移方程 dpi,j,k×(i+pp)(ak−1)pap(i−k)=dpi+p,j+1,pdp_{i, j, k} \times \displaystyle\binom{i + p}{p} (a^k - 1)^p a^{p(i - k)} = dp_{i + p, j + 1, p}。那么答案就是 ∑j=1nj∑k=1n−j+1dpn,j,k\displaystyle\sum_{j = 1}^n j \sum_{k = 1}^{n - j + 1} dp_{n, j, k}。
我们其实可以发现，jj 其实顶没用的（和我一样），只是在最后求答案时要乘以 jj。我们考虑 jj 的组合意义，就是在这 jj 层中选一层作为关键层。这是因为 (j1)=j\displaystyle\binom j1 = j。
现在我们可以改变 DP 的函数了，设 dpi,j,0/1dp_{i, j, 0 / 1} 表示给前 ii 个数分层，上一层有 jj 个数，且是否选择过关键层的答案，dpi,j,0dp_{i, j, 0} 到 dpi+p,p,0dp_{i + p, p, 0}，dpi,j,1dp_{i, j, 1} 到 dpi+p,p,1dp_{i + p, p, 1} 直接用之前的转移方程。对于每一层，都可以选择这一层成为关键层，于是把 dpi,j,0dp_{i, j, 0} 按照转移方程加到 dpi+p,p,1dp_{i + p, p, 1} 就可以了，复杂度降低到 O(n3)O(n^3)，足以通过此题。
完整代码：
CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...