刷题记录

沙雕的\(\text{ViXbob}\)又开启了新一轮的刷题计划呢。

如何优雅地求和

首先有个结论: \[ x^in^{\underline{i}}=\sum_{k=0}^nk^{\underline{i}}\binom{n}{k}x^k(1-x)^{n-k} \] 证明如下: \[ \begin{aligned}&\sum_{k=0}^nk^{\underline{i}}\binom{n}{k}x^k(1-x)^{n-k}\\=&xn\sum_{k=0}^{n-1}(k-1)^{\underline{i-1}}\binom{n - 1}{k-1}x^{k-1}(1-x)^{n-1-(k-1)}\\=&\cdots\end{aligned} \] 我们每次都提一个\(x, (n-z)\),最后就是\(x^in^{\underline{i}}\)

所以问题就变成了如何把给出的多项式转成一个下降幂多项式。左转模板假如这个\(m\)次下降幂多项式为: \[ h(x)=\sum_{i=0}^mh_ix^{\underline{i}} \] 那么答案为:\(\sum_{i=0}^mx^in^{\underline{i}}h_i\)

现在考虑怎么求\(h(x)\)。现我们梦见构造了一个多项式: \[ \begin{aligned}g(x)=&\sum_{i=0}^mf(i)\frac{x^i}{i!}\\=&\sum_{i=0}^m\frac{x^i}{i!}\sum_{j=0}^ih_ji^{\underline{j}}\\=&\sum_{j=0}^mh_j\sum_{i=j}^m\frac{x^i}{(i-j)!}\\=&\sum_{j=0}^mh_jx^j\sum_{i=j}^m\frac{x^{i-j}}{(i-j)!}\\=&h(x)e^x\end{aligned} \] 然后\(h(x)=g(x)e^{-x}\)

PS:\(e^{-x}=\sum_{i=}^{\infty}(-1)^i\frac{x^i}{i!}\)

然后做一遍卷积,把\(h_i\)求出来就好了。复杂度\(O(m\log m)\)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
/*
* 269.cpp
* This file is part of 269
*
* Copyright (C) 2019 - ViXbob
*
* 269 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 269 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 269. If not, see <http://www.gnu.org/licenses/>.
*/



/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define inv(x) (ksm(x, P - 2))

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 1e5 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;
const int maxm = maxn << 2;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

int n, m, x, a[maxn], fac[maxn], ifac[maxn], ans;

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int mul(int x, int y) { return 1ll * x * y % P; }
inline int ksm(int x, int k, int rnt = 1) {
for(int i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
return rnt;
}

namespace NTT {
const int G = 3, invG = inv(G);
int rev[maxm], E[maxm], H[maxm], s, l, inv;

inline void init(int n) {
s = 2; l = 1;
while(s <= n) s <<= 1, l++; inv = inv(s);
rep(i, 0, s - 1) rev[i] = rev[i >> 1] >> 1 | (i & 1) << l - 1;
memset(E, 0, sizeof(int) * (s + 5));
memset(H, 0, sizeof(int) * (s + 5));
}

inline void dft(int *a, int n, int f) {
rep(i, 0, n - 1) if(i < rev[i]) swap(a[i], a[rev[i]]);
for(int i = 1; i < n; i <<= 1) {
int Wn = ksm(f, (P - 1) / (i << 1));
for(int j = 0; j < n; j += (i << 1)) {
int w = 1;
for(int k = 0; k < i; k++, w = 1ll * w * Wn % P) {
int A1 = a[j + k], A2 = 1ll * a[j + k + i] * w % P;
a[j + k] = pls(A1, A2); a[j + k + i] = dec(A1, A2);
}
}
}
}

inline void conv() {
dft(E, s, G); dft(H, s, G);
rep(i, 0, s - 1) E[i] = 1ll * E[i] * H[i] % P;
dft(E, s, invG);
rep(i, 0, s - 1) E[i] = 1ll * E[i] * inv % P;
}
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read(); m = read(); x = read();
fac[0] = 1;
rep(i, 1, m) fac[i] = 1ll * fac[i - 1] * i % P;
ifac[m] = inv(fac[m]);
dep(i, m - 1, 0) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
NTT :: init(m << 1);
rep(i, 0, m) NTT :: E[i] = 1ll * read() * ifac[i] % P;
for(int i = 0, ty = 1; i <= m; i++, ty = (ty == 1 ? P - 1 : 1)) NTT :: H[i] = 1ll * ty * ifac[i] % P;
NTT :: conv();
rep(i, 0, m) a[i] = NTT :: E[i];
for(int i = 0, down = 1, mi = 1; i <= m; down = 1ll * down * (n - i) % P, mi = 1ll * mi * x % P, i++)
ans = pls(ans, 1ll * down * a[i] % P * mi % P);
cout << ans << endl;
return 0;
}