P8768 [蓝桥杯 2021 国 A] 积木 题解

· · 题解

首先有一个观察是 1\sim x-1、x\sim y、y+1\sim n 这三段可以分开考虑贡献再合并。
容易发现 y + 1\sim n 这一段对答案的贡献是 (R - L + 1) ^{n - y}，由于没有限制。

随后考虑前两个部分如何计算。

首先可以发现，从第二行开始，每一行的积木数量都落在一个区间 [l_i,r_i] 内。我们尝试生成积木数量的计数。首先设 f(t) = \sum_{i=L}^R t^i。不难得到第 n 行的生成函数为 f(t)^{n-1}。

我们发现目前的生成函数的最低项是非常数项，因此不妨将系数进行偏移。令

f(t) = \sum_{i=0}^{R-L}t^i = \frac{1 - t^{R-L+1}}{1-t}

第 n 行的生成函数为 f(t)^{n-1}，这样 [t^k]\left(f(t)^n\right) 对应的就是第 n+1 行放 k + w + n L 个积木的计数了。

然后可以枚举 k 表示第 x 行积木数量偏移后为 k 的计数，并以此生成第 y 行积木数量偏移后的值 r。我们可以将 r 进行二次偏移，随后提取 f(x)^{y-x} 的第 r 项系数。
依照上方描述，有 r = z\times (k + w + (x - 1) \times L) - (k + w + (y - 1)\times L)。

前两部分的答案就是

\sum_{k\ge 0} [t^k]\left(f(t)^{x-1}\right)\times [t^r]\left(f(t)^{y-x}\right)

你可能要问了：上界呢？
求和的上界是偏移后的上界，也就是 f(t)^n 最高的度数。f(t) 的度数最大是 R - L，在自乘最多 n 次后得到求和上界 N = n(R - L)。

发现 N 最高可能达到 2\times 10^7 的范围，直接做 NTT 的复杂度是 O(N\log N)，显然过不去。
你问这个方法怎么做？我们发现对 f(t) 的操作只有求幂运算，不难想到首先将 f 进行 DFT 后对点值求幂，再 IDFT 回来。这样就三次 DFT 得到答案。Submission.

多项式的次数无法降低，我们就需要寻找一种方法 O(n) 地递推出它的系数。

不妨考虑较广泛的情况，即递推

g(x) = \left(\frac{1 - x^n}{1-x}\right)^m

的前 k 项系数。

通过与P5434类似的手法，我们可以得到

g'(x) &= \left(\left(\frac{1 - x^n}{1-x}\right)^m\right)' \\ & = m\left(\frac{1 - x^n}{1-x}\right)^{m-1}\left(\frac{1 - x^n}{1-x}\right)' \\ & = m\left(\frac{1 - x^n}{1-x}\right)^{m-1}\left(\frac{(1 - x^n) - nx^{n-1} (1-x)}{(1-x)^2}\right) \\ & = m\ g(x)\left(\frac{1 - x^n}{1-x}\right)^{-1}\left(\frac{1 - x^n - nx^{n-1} + nx^n}{(1-x)^2}\right) \\ & = m\ g(x)\left(\frac{1 - nx^{n-1} + (n-1) x^n}{(x - 1)(x^n - 1)}\right) \end{aligned}

即

(x - 1)(x^n - 1)g'(x) = m\left(1 - nx^{n-1} + (n-1) x^n\right) g(x)

这自然导出了递推方案。因此可以做到 O(N) 递推。

统计答案并非瓶颈，因此做到了 O(n(R - L)) 求解本题。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (register int i = (a), i##_ = (b) + 1; i < i##_; ++i)
#define pre(i,a,b) for (register int i = (a), i##_ = (b) - 1; i > i##_; --i)
const int N = 2e7 + 10, mod = 998244353, g = 3;
int n, www, l, r, x, y, z, A[N], B[N], ans, len, lim;
int inv[N];

int qp(int a, int b) {
    int ret = 1;
    while (b) {
        if (b & 1) ret = 1ll * ret * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    } return ret;
}

void get(int f[], int n, int m) {
    f[0] = 1; 
    rep(i,1,len) {
        f[i] = f[i - 1];
        if (i - n + 1 >= 0) f[i] = (f[i] - 1ll * n * f[i - n] % mod + mod) % mod;
        if (i - n >= 0)     f[i] = (f[i] + 1ll * (n - 1) * f[i - n - 1]) % mod;
        f[i] = 1ll * f[i] * m % mod;

        if (i - 1 >= 0)     f[i] = (f[i] + 1ll * (i - 1) * f[i - 1]) % mod;
        if (i - n >= 0)     f[i] = (f[i] + 1ll * (i - n) * f[i - n]) % mod;
        if (i - n - 1 >= 0) f[i] = (f[i] - 1ll * (i - n - 1) * f[i - n - 1] % mod + mod) % mod;
        f[i] = 1ll * f[i] * inv[i] % mod;
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> www >> l >> r >> x >> y >> z;
    len = n * (r - l) + 1;
    inv[0] = inv[1] = 1;
    rep(i,2,len) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;

    get(A, r - l + 1, x - 1);
    get(B, r - l + 1, y - x);

    for (int i = 0, p; i < len; ++ i) {
        p = z * (www + (x - 1) * l + i) - (www + (y - 1) * l + i);
        if (p < 0) continue; if (p >= len) break;
        ans = (ans + 1ll * A[i] * B[p]) % mod;
    } cout << 1ll * ans * qp(r - l + 1, n - y) % mod;
}