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

· · 题解

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 类：

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

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

发现什么？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;
}