洛谷题解说这题是“巨大蠢题。这是我见过的最垃圾的 ARC，没有之一。”
好吧，我不会做巨大蠢题。
首先我们可以想到，如果 \(|a_i - a_j| = m\)，那么 \(a_i\) 和 \(a_j\) 一定在关于 \(m\) 的同一剩余系下。所以我们可以将这 \(n\) 个数分成若干个剩余系进行考虑。而我们发现，这相当于将每个剩余系的一些数划分成若干条链，然后链的总长度就是 \(|a_i - a_j| = m\) 的个数。
但是我们发现，划分成的两个链之间也有可能存在 \(|a_i - a_j| = m\)，那么以上其实求的是至少，那么二项式反演一下即可。
如何求将 \(n\) 个数划分成 \(k\) 条链，且每个长度 \(\ge 2\) 的链使方案数 \(\times 2\)，这样所有划分的总方案数呢？不会组合意义就生成函数，\(F(x)=x+2x^2+2x^3+2x^4+\cdots = \frac{2x}{1 - x} - x\)，求 \([x^n] F(x)^k\)，大力展开系数可得到：
\[f_k=\sum_{i=0}^k \binom{k}{i}(-1)^i\binom{n-i-1}{k-i-1} 2^{k - i} \]这东西 NTT 算就行。
每个剩余系直接 EGF 乘起来合并。
然后二项式反演回去即可。
我没想到咋算划分方案数。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000005;
const int P = 998244353, G = 3;
int qpow(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = 1ll * ans * a % P;
a = 1ll * a * a % P;
b >>= 1;
}
return ans;
}
const int GI = qpow(G, P - 2);
int r[MAXN];
struct Polynomial {
vector<int> a;
int len;
Polynomial(int len = 0) : len(len) { a.resize(len + 1); }
void set(int len) { this->len = len; a.resize(len + 1); }
int& operator[](int b) { return a[b]; }
void ntt(int limit, bool rev) {
set(limit);
for (int i = 0; i < limit; i++)
if (i < r[i]) swap(a[i], a[r[i]]);
for (int mid = 1; mid < limit; mid <<= 1) {
int step = qpow(rev ? GI : G, (P - 1) / (mid << 1));
for (int l = 0; l < limit; l += (mid << 1)) {
int w = 1;
for (int i = 0; i < mid; i++, w = 1ll * w * step % P) {
int x = a[l + i], y = 1ll * w * a[l + i + mid] % P;
a[l + i] = (x + y) % P, a[l + i + mid] = (x - y + P) % P;
}
}
}
if (rev) {
int inv = qpow(limit, P - 2);
for (int i = 0; i < limit; i++)
a[i] = 1ll * a[i] * inv % P;
}
}
Polynomial operator*(Polynomial b) {
Polynomial a = *this, c;
int len = a.len + b.len;
int limit = 1;
while (limit <= len) limit <<= 1;
for (int i = 1; i < limit; i++)
r[i] = (r[i >> 1] >> 1) | ((i & 1) * limit >> 1);
a.ntt(limit, 0), b.ntt(limit, 0);
c.set(limit);
for (int i = 0; i < limit; i++)
c[i] = 1ll * a[i] * b[i] % P;
c.ntt(limit, 1);
c.set(len);
return c;
}
Polynomial operator^(int b) {
Polynomial a = *this, ans;
ans[0] = 1;
while (b) {
if (b & 1) ans = ans * a;
a = a * a;
b >>= 1;
}
return ans;
}
void print() {
for (int i : a)
printf("%d ", i);
printf("\n");
}
};
int n, m;
int fac[MAXN], inv[MAXN];
Polynomial calc(int n) {
Polynomial f(n), g(n);
for (int i = 0; i < n; i++) {
f[i] = 1ll * inv[i] * ((i & 1) ? P - 1 : 1) % P * fac[n - i - 1] % P * qpow((P + 1) / 2, i) % P;
}
for (int i = 1; i <= n; i++) {
g[i] = 1ll * inv[i] * inv[i - 1] % P;
}
f = f * g;
f.set(n);
for (int i = 0; i <= n; i++) {
f[i] = 1ll * f[i] * qpow(2, i) % P * fac[i] % P * inv[n - i] % P;
}
f[n] = 1;
return f;
}
int main() {
scanf("%d%d", &n, &m);
fac[0] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = 1ll * fac[i - 1] * i % P;
}
inv[n] = qpow(fac[n], P - 2);
for (int i = n; i >= 1; i--) {
inv[i - 1] = 1ll * inv[i] * i % P;
}
int q = n % m;
Polynomial ans = (calc(n / m + 1) ^ q) * (calc(n / m) ^ (m - q));
for (int i = 0; i <= n; i++) {
ans[i] = 1ll * ans[i] * fac[i] % P;
}
Polynomial f(ans.len), g(ans.len);
for (int i = 0; i <= n; i++) {
f[i] = 1ll * ans[n - i] * fac[i] % P;
g[i] = 1ll * inv[n - i] * (((n - i) & 1) ? P - 1 : 1) % P;
}
f = f * g;
for (int i = 0; i < n; i++) {
printf("%lld ", 1ll * f[n + i] * inv[i] % P);
}
return 0;
}