又是多项式重工业。
题意:求所有长度为 的序列满足每一个数都在 且互不相等的权值和。权值定义为每一个数的乘积。你需要输出 的答案,,,3s。
看到不等,那么每一个数最多出现一次,并且可以转为无序,于是最后答案要乘上 。
考虑其生成函数为 ,但是规模过大,无法分治 NTT。
考虑经典取 ,那么我们现要求出 。对其泰勒展开,可以得到:
下面我们需要干的事情就是求 。
考虑其 EGF,我们可以得到:
最后一步等比求和一下,可以得到 。直接求逆即可,注意常数项都为 0,需要向低移一位。
其实 的下界不重要,因为我们最后取的一定是 的答案,和 0 没有关系。注意 EGF 最后需要乘上 。
如果你被卡常的话,请将 和 手动计算,一般常数正常的都能过。(总感觉话没说对……)
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 ...