CF955F Cowmpany Cowmpensation

前言

我居然切出了一道Div 1的F,哈哈哈…

题意

[1,D]中的数字给一棵N个节点树上的点标号,要求每个节点的标号不得大于它的父节点,求标号的方案数。
1\le D\le 10^9,\space N\le 3000

分析

我们先考虑一个树形DP,设f[u][i]表示节点u标号为i的方案数,那么f[u][i]=\prod\limits_{v\in son_u}\sum\limits_{j\le i}f[v][j].
如果设g[u][i]=\sum\limits_{j=1}^i f[u][j],方程就变成了f[u][i]=\prod\limits_{v\in son_u}g[v][i]. 但是D很大,不可能直接DP,接下来介绍两种方法绕过这个数据范围。

容斥

因为N很小,事实上树中用到的标号种树不会超过N,远小于D. 我们利用一个离散化的思想,稍微更改一下上面的DP方程,设f[u][i]表示节点u子树中标号种数不超过i的方案数(可以将i看做是离散化后的标号),那么我们求出答案后乘上{D\choose i}就是实际的方案数了。
但是这样会有重复,因为我们设的是不超过而不是恰好。令f(x)=f[1][x]表示树中用到的标号种数至多为x种的方案数,g(x)表示恰好x种的方案数。f(x)g(x)满足这样的关系:f(x)=\sum\limits _{i=1}^n{n-1\choose i-1}g(i). 注意这里的系数是{n-1\choose i-1},这是因为f(x)实际上钦定了根节点就是离散后的最大的标号,因此最大的标号必须被选上。反演一下得到:g(n)=\sum\limits_{i=1}^n(-1)^{n-i}{n-1\choose i-1}f(i).
答案就是\sum\limits_{i=1}^n {D\choose i}g(i).
时间复杂度:O(n^2).

插值

这里有一个不容易发现的性质,就是答案是一个关于D的N次多项式。再详细一些,就是f[u][i]是一个关于i次数为子树大小减一的多项式,g[u][i]是一个关于i次数等于子树大小的多项式。
这里用归纳法证明:

  • 对于叶子节点,显然成立。
  • 我们考虑转移的过程,f[u][i]=\prod\limits_{v\in son_u}g[v][i],关于f的结论成立;因为g实际为f的前缀和,因此次数加一。

这样我们就可以DP出f/g[1][1..N+1],然后插值即可。

参考程序

最近写组合的题好像经常出锅啊,要么忘记取模,要么没转LL…
两种方法好多代码都是可以共用的,不过写起来肯定是插值法快。

容斥法

#define pb push_back
typedef long long LL;

int N, D, f[MAXN][MAXN], g[MAXN][MAXN], fac[MAXN], inv[MAXN];
std::vector<int> G[MAXN];

inline LL C(int n, int r) { return (LL)fac[n] * inv[r] % MOD * inv[n - r] % MOD; }
inline void mult(int &x, int y) { x = (LL)y * x % MOD; }
inline void add(LL &x, LL d) { (x += d) %= MOD; }
LL BigC(int n, int r) {     // C(D, i)直接暴力算
    LL res = inv[r];
    for (LL i = n - r + 1; i <= n; i++) (res *= i) %= MOD; 
    return res;
}
void init();
void dfs(int);

int main() {
    init();
    using FastIO::read;

    read(N), read(D);
    for (int i = 2, fa; i <= N; i++) {
        read(fa);
        G[fa].pb(i);
    }
    dfs(1);

    LL ans = 0;
    for (int i = 1; i <= N && i <= D; i++) {
        LL tmp = 0;
        for (int j = 1; j <= i; j++) add(tmp, (i - j & 1 ? -1LL : 1LL) * C(i - 1, j - 1) * f[1][j] % MOD);  
        tmp = (tmp + MOD) % MOD;
        add(ans, tmp * BigC(D, i) % MOD);
    }
    ans = (ans + MOD) % MOD;
    std::cout << ans << std::endl;
    return 0;
}

void dfs(int u) {
    for (int i = 1; i <= N; i++) f[u][i] = 1;
    for (auto v : G[u]) {
        dfs(v);
        for (int i = 1; i <= N; i++) mult(f[u][i], g[v][i]);
    }
    for (int i = 1; i <= N; i++) g[u][i] = (g[u][i - 1] + f[u][i]) % MOD;
}

LL fast_pow(LL bs, int ex) {
    LL res = 1;
    for (; ex; (bs *= bs) %= MOD, ex >>= 1) if (ex & 1) (res *= bs) %= MOD;
    return res;
}

void init() {
    fac[0] = 1;
    for (LL i = 1; i <= INIT; i++) fac[i] = i * fac[i - 1] % MOD;   
    inv[INIT] = fast_pow(fac[INIT], MOD - 2);
    for (LL i = INIT - 1; i >= 0; i--) inv[i] = (i + 1) * inv[i + 1] % MOD;
}

插值法

inline LL get_inv(LL x) { return fast_pow(x, MOD - 2); }
void init();
void dfs(int);

int main() {
    // ...(input & init)
    dfs(1);

    if (D <= N + 1) {
        std::cout << g[1][D] << std::endl;
        return 0;
    }
    LL prd = 1, ans = 0;
    for (LL i = D - N - 1; i < D; i++) (prd *= i) %= MOD;
    for (int i = 1; i <= N + 1; i++) {
        LL tmp = prd * get_inv(D - i) % MOD, ivv = (LL)inv[i - 1] * inv[N + 1 - i] % MOD;
        // 这里插值的时候全部乘一起容易爆LL(622F也是这样),分开算比较好
        (ans += (LL)g[1][i] * ivv % MOD * tmp % MOD * (N + 1 - i & 1 ? -1LL : 1LL)) %= MOD;
    }
    ans = (ans + MOD) % MOD;
    std::cout << ans << std::endl;
    return 0;
}

void dfs(int u) {
    for (int i = 1; i <= N + 1; i++) f[u][i] = 1;
    for (auto v : G[u]) {
        dfs(v);
        for (int i = 1; i <= N + 1; i++) mult(f[u][i], g[v][i]);
    }
    for (int i = 1; i <= N + 1; i++) g[u][i] = (g[u][i - 1] + f[u][i]) % MOD;
}

void init() {
    fac[0] = 1;
    for (LL i = 1; i <= INIT; i++) fac[i] = i * fac[i - 1] % MOD;
    inv[INIT] = get_inv(fac[INIT]);
    for (LL i = INIT - 1; i >= 0; i--) inv[i] = (i + 1) * inv[i + 1] % MOD;
}

总结

这道题方法很灵活,不过核心思想都是树形DP,容斥方法想起来相对简单(不过离散思想也算是套路),当然要注意组合系数很容易写错;插值法不容易想到,但是代码实现简单很多。这是道好题!

About The Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注