闲话
今日闲话写一部分发一部分（
所以常来看看！
还是杂题（
题面长，不粘。
首先有一个观察是 \(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(x) = \sum_{i=L}^R x^i\)。不难得到第 \(n\) 行的生成函数为 \(f(x)^{i-1}\)。
我们发现目前的生成函数的最低项是非常数项。不妨将系数进行偏移，令 \(f(x) = \sum_{i=0}^{R-L}x^i\)，第 \(n\) 行的生成函数为 \(f(x)^{n-1}\)，这样 \([x^k]\left(f(x)^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} [x^k]\left(f(x)^{x-1}\right)\times [x^r]\left(f(x)^{y-x}\right) \]你可能要问了：上界呢？
求和的上界是偏移后的上界，也就是 \(f(x)^n\) 最高的度数。\(f(x)\) 的度数最大是 \(R - L\)，在自乘最多 \(n\) 次后得到求和上界 \(N = n(R - L)\)。
发现 \(N\) 最高可能达到 \(2e7\) 的范围，直接做 NTT 的复杂度是 \(O(N\log N)\)，显然过不去。
你问怎么做？我们发现对 \(f(x)\) 的操作只有求幂运算，不难想到首先将 \(f\) 进行 DFT 后对点值求幂，再 IDFT 回来。这样就三次 DFT 得到答案。
code
#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;
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;
}
int btrs[N];
int initrs(int k) {
int len = 1; while (len < k) len <<= 1;
for (int i = 0; i < len; ++ i)
btrs[i] = (btrs[i >> 1] >> 1) | ((i & 1) ? len >> 1 : 0);
return len;
}
const int L = 1 << 21;
int w[2][L];
int IUR() {
w[0][0] = w[1][0] = 1;
int w0 = qp(g, (mod - 1) / L);
for (int i = 1; i < L; ++ i) w[0][L - i] = w[1][i] = 1ll * w[1][i-1] * w0 % mod;
return 1;
} int dummy = IUR();
void NTT(int A[], int len, int type) {
for (int i = 0; i < len; ++ i) if (i < btrs[i]) swap(A[i], A[btrs[i]]);
for (int mid = 1; mid < len; mid <<= 1) {
for (int i = L / (mid << 1), j = 0; j < len; j += (mid << 1)) {
for (int k = 0; k < mid; ++ k) {
int x = A[j + k], y = 1ll * A[j + k + mid] * w[type][i * k] % mod;
A[j + k] = (x + y) % mod;
A[j + k + mid] = (x - y + mod) % mod;
}
}
} if (type == 1) return ;
int tmp = qp(len, mod - 2);
for (int i = 0; i < len; ++ i) A[i] = 1ll * A[i] * tmp % mod;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> www >> l >> r >> x >> y >> z;
int len = n * (r - l) + 1, lim = initrs(len);
rep(i,0,r - l) A[i] = 1;
NTT(A, lim, 1);
for (int i = 0; i < lim; ++ i) B[i] = qp(A[i], y - x), A[i] = qp(A[i], x - 1);
NTT(A, lim, 0), NTT(B, lim, 0);
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 >= lim) break;
ans = (ans + 1ll * A[i] * B[p]) % mod;
} cout << 1ll * ans * qp(r - l + 1, n - y) % mod;
}
多项式的次数无法降低，我们就需要寻找一种方法递推出它的系数。
不妨考虑较广泛的情况，即递推
\[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))\) 求解本题。
code
常数有点大，目前是 lg 最劣解（
#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;
}