专栏文章

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

PPetit_Souris
P12445题解参与者 3已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@mip1cs3o
此快照首次捕获于
2025/12/03 04:33
3 个月前
此快照最后确认于
2025/12/03 04:33
3 个月前
查看原文
很考验基本功的计数题。
先考虑 k=nk = n 怎么做。省选 2025 D2T2 再次警醒我们，DAG 上每个点都有经过他的 1→n1\to n 的路径等价于每个点都有入边和出边，除了 1,n1, n。
两个限制不方便同时处理，这时候可以考虑容斥。比如说我们强制规定一些点违反限制，入度必须为 00。这时候可以直接从后往前 dp：设 dpi,jdp_{i, j} 表示 [i,n][i, n] 中的点，强制违反了 jj 个点。那么对于 ii 连边时，就是在 n−i−jn - i - j 个没有强制违反的点中任意取一个子集。最后系数为 (−1)j(-1) ^ j。
这样可以求出所有 ii 个点的 k=ik = i 的答案，设为 fif_i。
现在考虑 k<nk < n 的情况。那么我们先选出一个 kk 个点的方案 fkf_k，再考虑剩下的点。因此所有点可以分为三类：
  • 11 类点：1→x→n1\to x \to n 的点；
  • 22 类点：1→x1 \to x，但是 x→nx \to n 不成立；
  • 33 类点：1→x1\to x 不成立。
考虑 1−11-1 以外的连边。发现 33 可以往后面任意点连边，而 1,21,2 都只能向后面 22 连边。
因此我们可以这样倒过来 dp：设 gi,j,kg_{i, j, k} 表示 [i,n][i, n] 中，目前有 jj 个 11，kk 个 22 的方案数。这样是 O(n3)\mathcal O(n ^ 3) 的。
但是我们发现 33 类点的贡献只跟位置相关，是一个 2n−i2^{n - i} 的形式。也就是说我们可以做一个分步转移：
首先求出 gi,jg_{i, j} 表示 ii 个 1,21, 2 类点，目前 jj 个 11 类点的方案数；再求出 hi,jh_{i, j} 表示 ii 个点中选出 jj 个 33 类点，贡献之和。最后再把 f,g,hf, g, h 结合起来就容易计算出答案。
时间复杂度 O(n2)\mathcal O(n ^ 2)。
CPP
#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;
}

评论

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

正在加载评论...