题解：P12445 [COTS 2025] 数好图 / Promet

注意到若把整张 DAG 分成三类点，一类是符合题目条件的点，一类是从 1 号点可以到达的点，一类是从 1 号点不可到达的点。那么合法点连边方法有 ① -> ②，③ -> ①，③ -> ②。他们之间相互独立，也就是不同类之间的连边合法性只与类的种类有关，故可以将他们分开考虑，再进行合并，以降低问题复杂度。

考虑全为 ① 类点，即只

k = n

的情况怎么做。容易地设计

O(n^3)

的 dp：

f(i,j)

表示前

i

个点，有

j

个不同分支（即有

j

个出度为 0 的点），DAG 的方案数。枚举

k

表示前面连接了多少出度为 0 的点，

f(i,j) = \sum f(i-1,j+k-1) \times C_{j+k-1}^{k} \times 2^{(i-1)-(j+k-1)}

。~~我会FFT~~但是难以优化。

所以难以想到用容斥原理的思路设计状态。相当于维护每个节点入度出度不为 0，保证入度不为 0 是好做的。我们主要要维护出度为 0 的点，那么设

f(i,j)

为前

i

个点，钦定

j

个点出度为 0，那么可以转移

f(i,j) = f(i-1,j) \times (2^{i-1-j}-1) + f(i-1,j-1) \times (2^{i-j}-1)

，然后通过容斥公式用

f(i)

计算出使用

i

个点，没有出度为 0 的点的 DAG 的方案数。时间复杂度

O(n^2)

。

若加入 ② 类点，就相当于在 ① 类点有

i

个的基础上，将方案数乘上

j

个 ② 类点自己连边和与 ① 类点连边的方案数，得到符合条件的点数为

i

，总点数为

i+j

的答案。这直接 dp 就好了。加 ③ 类点同理。具体写法看代码。

这个故事告诉我们，对计数 dp 的优化束手无策的时候，也许可以试试容斥。

CPP

#include <bits/stdc++.h>
using namespace std;
int n, p;
int fac[2002], inv[2002], invfac[2002];
void init(){
	fac[0] = 1, inv[1] = 1, invfac[0] = 1;
	for(int i=1;i<=2000;i++) fac[i] = 1ll * fac[i-1] * i % p;
	for(int i=2;i<=2000;i++) inv[i] = (1ll * (-p/i) * inv[p%i] % p + p) % p;
	for(int i=1;i<=2000;i++) invfac[i] = 1ll * invfac[i-1] * inv[i] % p;
}
int C(int x,int y){
	if(x < y || x < 0 || y < 0) return 0;
	return 1ll * fac[x] * invfac[y] % p * invfac[x-y] % p;
}
int ksm(int s,int cnt){
	int ret = 1;
	while(cnt){
		if(cnt&1) ret = 1ll * ret * s % p;
		s = 1ll * s * s % p;
		cnt >>= 1;
	}
	return ret;
}

int f[2002][2002], g[2002][2002]; // 前 i 个数，钦定 j 个没有出度
int S[2002]; 

int dp1[2002][2002], dg1[2002][2002], dp2[2002][2002];
int Ans[2002];

int main(){
	scanf("%d%d",&n,&p);
	init();
	
	f[0][0] = 1, g[0][0] = 1;
	f[1][0] = 1, f[1][1] = 1, g[1][0] = 1;
	for(int i=2;i<=n;i++) {
		for(int j=0;j<=i;j++) {
			if(i != j) f[i][j] = 1ll * f[i-1][j] * (ksm(2, i-j-1) - 1) % p;
			if(i != j) g[i][j] = 1ll * f[i-1][j] * (ksm(2, i-j-1) - 1) % p;
			if(j > 0) f[i][j] = (1ll * f[i][j] + 1ll * f[i-1][j-1] * (ksm(2, i-j) - 1) % p) % p;
		}
	}
	for(int i=0;i<=n;i++) {
		for(int j=0;j<=i;j++){
			if(j & 1) S[i] = ((1ll * S[i] - g[i][j]) % p + p) % p;
			else S[i] = (1ll * S[i] + g[i][j]) % p;
		}
	}
	
	dp1[0][0] = 1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=i;j++){
			dp1[i][j] = dp1[i-1][j];
			dg1[i][j] = dp1[i-1][j];
			if(i != 1 && i != n) dp1[i][j] = (dp1[i][j] + 1ll * dp1[i-1][j-1] * (ksm(2, i-1)-1) % p) % p;
		}
	}
	
	dp2[0][0] = 1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=i;j++){
			dp2[i][j] = 1ll * dp2[i-1][j] * ksm(2, j) % p;
			if(i != 1 && i != n && j != 0) dp2[i][j] = (dp2[i][j] + 1ll * dp2[i-1][j-1] * ksm(2, j-1) % p) % p;
		}
	}
	
	//S[i] * dg1[k][k-i] * dp2[n][n-k]
	for(int i=0;i<=n;i++){
		for(int k=i;k<=n;k++){
			Ans[i] = (Ans[i] + 1ll * S[i] * dg1[k][k-i] % p * dp2[n][n-k] % p) % p;
		}
	}
	Ans[0] = Ans[2];
	
	for(int i=0;i<=n;i++) printf("%d ",Ans[i]);
	
	return 0;
}

题解：P12445 [COTS 2025] 数好图 / Promet

文章操作

相关推荐

评论

题解：P12445 [COTS 2025] 数好图 / Promet