Luogu P5850 calc加强版

又是多项式重工业。

题意:求所有长度为 n 的序列满足每一个数都在 [1,k] 且互不相等的权值和。权值定义为每一个数的乘积。你需要输出 n[1,lim] 的答案,lim5×105k<998244353,3s。

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

考虑其生成函数为 i=1k(ix+1),但是规模过大,无法分治 NTT。

考虑经典取 ln,那么我们现要求出 i=1kln(ix+1)。对其泰勒展开,可以得到:

lnF(x)=i=1kln(ix+1)=i=1kj=1(1)j+1(ix)jj=j=1(1)j+1ji=1kij

下面我们需要干的事情就是求 i=1kij

考虑其 EGF,我们可以得到:

G(x)=j=0xjj!i=0kij=i=0kj=0(ix)jj!=i=0keix

最后一步等比求和一下,可以得到 G(x)=e(k+1)x1ex1。直接求逆即可,注意常数项都为 0,需要向低移一位。

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

如果你被卡常的话,请将 exe(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;
}

Gitalking ...