又是多项式重工业。
题意：求所有长度为 $n$ 的序列满足每一个数都在 $[1, k]$ 且互不相等的权值和。权值定义为每一个数的乘积。你需要输出 $n\in [1, lim]$ 的答案，$lim\leq 5\times 10 ^ 5$，$k< 998244353$，3s。
看到不等，那么每一个数最多出现一次，并且可以转为无序，于是最后答案要乘上 $n!$。
考虑其生成函数为 $\prod_{i = 1} ^ k (ix + 1)$，但是规模过大，无法分治 NTT。
考虑经典取 $\ln$，那么我们现要求出 $\sum_{i = 1} ^ k \ln(ix + 1)$。对其泰勒展开，可以得到：
下面我们需要干的事情就是求 $\sum_{i = 1} ^ k i ^ j$。
考虑其 EGF，我们可以得到：
最后一步等比求和一下，可以得到 $G(x) = \dfrac{e ^ {(k + 1)x} - 1}{e ^ x - 1}$。直接求逆即可，注意常数项都为 0，需要向低移一位。
其实 $i, j$ 的下界不重要，因为我们最后取的一定是 $[1, n]$ 的答案，和 0 没有关系。注意 EGF 最后需要乘上 $i!$。
如果你被卡常的话，请将 $e ^ x$ 和 $e ^ {(k + 1)x}$手动计算，一般常数正常的都能过。（总感觉话没说对……）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| int main()
{
inv[1] = fact[0] = 1;
for (int i = 1; i < N; ++ i) fact[i] = (LL) fact[i - 1] * i % Mod;
for (int i = 2; i < N; ++ i) inv[i] = (LL) (Mod - Mod / i) * inv[Mod % i] % Mod;
int n, k;
std::cin >> k >> n;
poly A(n + 2), B(n + 2);
A[1] = k + 1, A = Exp(A), A.erase(A.begin());
B[0] = 1;
for (int i = 1; i <= n + 1; ++ i) B[i] = (LL) B[i - 1] * inv[i + 1] % Mod;
A = A * Inv(B), A.resize(n + 1);
for (int i = 0; i <= n; ++ i) A[i] = (LL) A[i] * fact[i] % Mod;
for (int i = 1, op = 1; i <= n; ++ i, op = Mod - op)
A[i] = (LL) A[i] * inv[i] % Mod * op % Mod;
A[0] = 0, A = Exp(A);
for (int i = 1; i <= n; ++ i)
printf("%lld\n", (LL) A[i] * fact[i] % Mod);
return 0;
}
|