自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:15:37，当前版本为作者最后更新于2025-05-09 21:38:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Solution

我做这个题，花了将近 2 个小时……如此水平，如何 NOI！/ll

不过克罗地亚国家队在这道题上得分 $\max$ 为 $4$。

考虑 $k=n$ 怎么做，也就是所有点都在某一条 $1 \to n$ 路径上。

考虑让 $1$ 到 $n-1$ 每个点至少有一条出边，这样可以保证所有点都能到 $n$。而只要除了 $1$ 以外所有点入度都不是 $0$，就能保证 $1$ 能到达所有点。

那么直接施加容斥。设 $dp_{i,j}$ 为，考虑了后 $i$ 个点，有 $j$ 个点被钦定了入度为 $0$（特别的，倒数第 $i$ 个点此时不能被钦定，只能在转移的时候被钦定。即，$j < i$）。这个可以 $O(n^2)$ 做。

在 $O(n^2)$ 复杂度内，我们还可以算出 $t$ 个点构成的、满足所有点都在 $1$ 到 $t$ 路径上的 DAG 数量，设为 $g_t$。

对于 $k$ 更小的情况，考虑在 $g_k$ 的基础上增加点，使得仍然只有这 $k$ 个点满足要求。

将点划分为 $3$ 类：

• $1$ 类点，表示在 $1$ 到 $n$ 的路径上（即在我们钦定的 $k$ 个点之中）；
• $2$ 类点，表示能从 $1$ 到达的、但不是 $1$ 类点的点；
• $3$ 类点，表示不能从 $1$ 到达的点。

记 $op_i$ 表示这 $n$ 个点类型构成的序列，其中 $op_1=op_n=1$。我们还需要再 $op$ 中分配 $k-2$ 个 $1$，以及若干个 $2$ 和 $3$。对于每一种分配方式，我们计算所有额外边（不是 $1$ 类和 $1$ 类的连边）的连接方式，乘上 $g_k$，加到 $ans_k$ 中。

对于每个点，我们往前连边。

• $1$ 类点：可以往编号比他小的 $3$ 类点连边；
• $2$ 类点：可以往编号比他小的 $1$、$2$、$3$ 类点连边，且必须往至少一个 $1$ 或 $2$ 类点连边；
• $3$ 类点：可以往编号比他小的 $3$ 类点连边。

发现什么？$3$ 类点可以往其后面所有点连边。所以假设所有的 $3$ 类点在 $p_1$、$p_2$、$\cdots$、$p_z$ 处，可以产生的贡献为 $2^{\sum_{i=1}^z n-p_i}$。

因此我们可以 DP 求出所有的贡献之和，然后将 $3$ 类点删掉，只考虑 $1$、$2$ 类点之间的贡献。这也可以 $O(n^2)$ 暴力。

整体时间复杂度为 $O(n^2)$，足以通过本题。

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2000+10;
int n,MOD,dp[MAXN][MAXN],C[MAXN][MAXN],pw[MAXN*MAXN],ans[MAXN];
int mul[MAXN][MAXN],f[MAXN][MAXN],g[MAXN]; 
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>MOD;
	pw[0]=1; ffor(i,1,n*n) pw[i]=pw[i-1]*2%MOD;
	ffor(i,0,n) {
		C[i][0]=1;
		ffor(j,1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;	
	}
	dp[1][0]=1;
	ffor(i,2,n) ffor(j,0,i-1) {
		int mul=dp[i-1][j];
		if(j) mul=(mul+dp[i-1][j-1])%MOD;
		dp[i][j]=mul*(pw[i-j-1]-1)%MOD;
	}
	ffor(i,2,n) ffor(j,0,i) g[i]=(g[i]+dp[i][j]*(1-2*(j&1)))%MOD;
	mul[n][0]=1;
	roff(i,n-1,2) ffor(j,0,n) {
		mul[i][j]=mul[i+1][j];
		if(j) mul[i][j]=(mul[i][j]+mul[i+1][j-1]*pw[n-i])%MOD;
	}
	f[1][0]=1;
	ffor(i,1,n) ffor(j,(i==1),n-i) {
		f[i][j]=f[i-1][j],ans[i]=(ans[i]+mul[2][n-i-j]*f[i][j])%MOD;
		if(j) f[i][j]=(f[i][j]+f[i][j-1]*(pw[i+j-1]-1))%MOD;
	}
	ffor(i,2,n) ans[i]=ans[i]*g[i]%MOD;
	ans[0]=pw[n*(n-1)/2];
	ffor(i,2,n) ans[0]=(ans[0]-ans[i])%MOD;
	ffor(i,0,n) cout<<(ans[i]%MOD+MOD)%MOD<<' ';
	return 0;
}