2023.8.23 闲话

T1

给定长度为 $n$ 的序列 $a$，初始全为 $0$。共有 $m$ 次操作，一次操作 $(l,r,k)$ 会对于所有 $l\leq i\leq r$ 使得 $a_i$ 增加 $\dbinom{i+k-l}{k}$。求所有操作过后的 $a$ 数组。

$n,m\leq 5\times 10^5$，$k\leq 20$。

遇到组合数问题，先画杨辉三角。

发现这个区间加法可以转化到在第 $k+1$ 阶差分上进行单点修改。但是因为我们需要在 $>r$ 的位置上把差分补回来，需要修改一个直角三角形 $\mathcal{O}(k^2)$ 个点。

这就需要一个 tricky 的想法。由于只有一次查询，且查询的是第 $0$ 阶差分最后的形式，所以我们并不需要精确修改 $1\sim k+1$ 阶差分，只需要让最后做完 $k+1$ 次前缀和后的形式不变即可。

我们把每一阶差分上需要在 $>r$ 的位置上补齐的值全都放在第 $r+1$ 个位置上。这样每一阶差分只需要在 $r+1$ 上补一个前缀和。由于恒等式

$\displaystyle \sum_{i=0}^n\binom{i}{x}=\sum_{i=x}^n\binom{i}{x}=\binom{n+1}{x+1}$

画画图推推式子，发现只需要在第 $j$ 阶差分的第 $r+1$ 个位置上补 $-\dbinom{L+k-j}{k+1-j}$ 即可。其中 $L=r-l+1$。这样就只需要修改 $\mathcal{O}(k)$ 个点了。

时间复杂度 $\mathcal{O}(nk)$。

核心代码：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5 + 25, mod = 1e9 + 7;

int n, m, a[MAXN], c[MAXN][25], diff[25][MAXN];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n + 22; i++) {
        c[i][0] = 1;
        for (int j = 1; j <= min(i, 22); j++) 
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    }
    while (m--) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        int len = r - l + 1;
        diff[k + 1][l]++;
        diff[k + 1][r + 1]--;
        for (int j = 1; j <= k; j++) 
            diff[j][r + 1] = (diff[j][r + 1] - c[len + k - j][k + 1 - j] + mod) % mod;
    }
    for (int i = 20; i >= 0; i--) {
        for (int j = 1; j <= n; j++) {
            a[j] = (a[j - 1] + diff[i + 1][j]) % mod;
            diff[i][j] = (diff[i][j] + a[j]) % mod;
        }
    }
    for (int i = 1; i <= n; i++)
        printf("%d\n", diff[0][i]);
}

T2

求 $n$ 个点有标号无向图中，满足最大连通块节点数恰为 $k$ 的个数。

$n,k\leq 2\times 10^3$。

令 $g(i)$ 表示 $i$ 个点的无向图数量，那么显然有

$\displaystyle g(i)=2^{\binom{i}{2}}$

令 $f(i)$ 表示 $i$ 个点的无向连通图数量。考虑用总数减去不连通图的数量。

不连通图的充要条件是至少有两个连通块。为了避免算重，我们钦定 $1$ 号点所在连通块的大小为 $j$，那么只需要再选出 $j-1$ 个点与 $1$ 构成连通块。

$\displaystyle f(i)=g(i)-\sum_{j=1}^{i-1}\binom{i-1}{j-1}f(j)g(i-j)$

发现连通块大小恰好为 $k$ 是不好算的，而不超过 $k$ 是好算的，不妨把问题转化为不超过。

令 $dp(i)$ 表示 $i$ 个点的无向图数量，满足连通块大小不超过 $k$。仍然钦定 $1$ 号点所在连通块的大小，用一样的方法计算。

$\displaystyle dp(i)=\sum_{j=0}^k\binom{i-1}{j-1}f(j)dp(i-j)$

再对连通块大小不超过 $k-1$ 做一遍，答案相减即可。

时间复杂度 $\mathcal{O}(n^2+nk)$。

核心代码：

for (int i = 0; i <= n; i++) {
    g[i] = Pow(2, c[i][2]);
}
f[0] = 1;
for (int i = 1; i <= n; i++) {
    f[i] = g[i];
    for (int j = 1; j <= i - 1; j++) {
        int x = 1ll * f[j] * g[i - j] % mod * c[i - 1][j - 1] % mod;
        f[i] = (f[i] - x + mod) % mod;
    }
}
dp[0] = 1;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= k; j++) {
        int x = 1ll * f[j] * dp[i - j] % mod * c[i - 1][j - 1] % mod;
        dp[i] = (dp[i] + x) % mod;
    }
}
int ans = dp[n];
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= k - 1; j++) {
        int x = 1ll * f[j] * dp[i - j] % mod * c[i - 1][j - 1] % mod;
        dp[i] = (dp[i] + x) % mod;
    }
}
ans = (ans - dp[n] + mod) % mod;