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

· · 题解

很考验基本功的计数题。

先考虑 k = n 怎么做。省选 2025 D2T2 再次警醒我们，DAG 上每个点都有经过他的 1\to n 的路径等价于每个点都有入边和出边，除了 1, n。

两个限制不方便同时处理，这时候可以考虑容斥。比如说我们强制规定一些点违反限制，入度必须为 0。这时候可以直接从后往前 dp：设 dp_{i, j} 表示 [i, n] 中的点，强制违反了 j 个点。那么对于 i 连边时，就是在 n - i - j 个没有强制违反的点中任意取一个子集。最后系数为 (-1) ^ j。

这样可以求出所有 i 个点的 k = i 的答案，设为 f_i。

现在考虑 k < n 的情况。那么我们先选出一个 k 个点的方案 f_k，再考虑剩下的点。因此所有点可以分为三类：

考虑 1-1 以外的连边。发现 3 可以往后面任意点连边，而 1,2 都只能向后面 2 连边。

因此我们可以这样倒过来 dp：设 g_{i, j, k} 表示 [i, n] 中，目前有 j 个 1，k 个 2 的方案数。这样是 \mathcal O(n ^ 3) 的。

但是我们发现 3 类点的贡献只跟位置相关，是一个 2^{n - i} 的形式。也就是说我们可以做一个分步转移：

首先求出 g_{i, j} 表示 i 个 1, 2 类点，目前 j 个 1 类点的方案数；再求出 h_{i, j} 表示 i 个点中选出 j 个 3 类点，贡献之和。最后再把 f, g, h 结合起来就容易计算出答案。

时间复杂度 \mathcal O(n ^ 2)。

#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
template <class T>
using Ve = vector<T>;
#define ALL(v) (v).begin(), (v).end()
#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)
#define pb push_back
bool Mbe;
ll read() {
    ll x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
void write(ll x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
const ll N = 2009;
ll n, Mod, pw2[N], dp[N][N], f[N], dp2[N][N], ans[N];
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(), Mod = read();
    pw2[0] = 1;
    rep(i, 1, n) pw2[i] = pw2[i - 1] * 2 % Mod;
    dp[1][0] = 1, f[1] = 1;
    rep(i, 1, n - 1) {
        rep(j, 0, i - 1) {
            dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * (pw2[i - j] - 1)) % Mod;
        }
        rep(j, 0, i) {
            if(j & 1) f[i + 1] = (f[i + 1] - dp[i + 1][j] + Mod) % Mod;
            else f[i + 1] = (f[i + 1] + dp[i + 1][j]) % Mod;
        }
        rep(j, 0, i - 1) {
            dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j] * (pw2[i - j] - 1)) % Mod;
        }
    }
    dp2[0][0] = 1;
    rep(i, 0, n - 1) {
        rep(j, 0, i) {
            // 3
            if(i && i < n - 1) dp2[i + 1][j + 1] = (dp2[i + 1][j + 1] + dp2[i][j] * pw2[n - i - 1]) % Mod;
            // !3
            dp2[i + 1][j] = (dp2[i + 1][j] + dp2[i][j]) % Mod;
        }
    } 
    memset(dp, 0, sizeof(dp));
    dp[1][1] = 1;
    rep(i, 1, n - 1) {
        rep(j, 1, i) {
            // 1
            dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j]) % Mod;
        }
        rep(j, 2, i + 1) {
            ans[j] = (ans[j] + dp[i + 1][j] * dp2[n][n - (i + 1)] % Mod * f[j]) % Mod;
            // if(j == 2) cout << i << " " << dp[i + 1][j] << " " << dp2[n][n - (i + 1)] << " " << f[j] << endl;
        }
        rep(j, 1, i) {
            // 2
            dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * (pw2[i] - 1)) % Mod;
        }
    }
    ans[0] = ans[2];
    rep(i, 0, n) write(ans[i]), putchar(' ');
    putchar('\n');
    cerr << "\n" << clock() * 1.0 / CLOCKS_PER_SEC * 1000 << "ms\n";
    return 0;
}