Luogu P5850 calc加强版

又是多项式重工业。

题意：求所有长度为 $n$ 的序列满足每一个数都在 $[1,k]$ 且互不相等的权值和。权值定义为每一个数的乘积。你需要输出 $n\in [1,lim]$ 的答案，$lim\le 5\times {10}^5$，$k<998244353$，3s。

看到不等，那么每一个数最多出现一次，并且可以转为无序，于是最后答案要乘上 $n!$。

考虑其生成函数为 $\prod _{i=1}^k(ix+1)$，但是规模过大，无法分治 NTT。

考虑经典取 $\ln$，那么我们现要求出 $\sum _{i=1}^k\ln (ix+1)$。对其泰勒展开，可以得到：

$$\begin{array}{rl}\ln F(x)=& \sum _{i=1}^k\ln (ix+1)\\ =& \sum _{i=1}^k\sum _{j=1}{\displaystyle \frac{(-1{)}^{j+1}(ix{)}^j}{j}}\\ =& \sum _{j=1}{\displaystyle \frac{(-1{)}^{j+1}}{j}}\sum _{i=1}^k{i}^j\end{array}$$

下面我们需要干的事情就是求 $\sum _{i=1}^k{i}^j$。

考虑其 EGF，我们可以得到：

$$\begin{array}{rl}G(x)=& \sum _{j=0}{\displaystyle \frac{x^j}{j!}}\sum _{i=0}^k{i}^j\\ =& \sum _{i=0}^k\sum _{j=0}{\displaystyle \frac{(ix{)}^j}{j!}}\\ =& \sum _{i=0}^k{e}^{ix}\end{array}$$

最后一步等比求和一下，可以得到 $G(x)={\displaystyle \frac{e^{(k+1)x}-1}{e^x-1}}$。直接求逆即可，注意常数项都为 0，需要向低移一位。

其实 $i,j$ 的下界不重要，因为我们最后取的一定是 $[1,n]$ 的答案，和 0 没有关系。注意 EGF 最后需要乘上 $i!$。

如果你被卡常的话，请将 $e^x$ 和 $e^{(k+1)x}$手动计算，一般常数正常的都能过。（总感觉话没说对……）

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;
}