自动搬运

查看原文

来自洛谷，原作者为

	joke3579 **

搬运于2025-08-24 22:42:16，当前版本为作者最后更新于2023-01-07 23:14:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

首先有一个观察是 $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类似的手法，我们可以得到

$$\begin{aligned} 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;
}