多项式的快速插值和求值

多项式的求值即给出一支多项式$\rm{F}$,同时给出多个$x$求出相应的${\rm{F}}_{[x]}$

多项式的插值即给出$n+1$个点对$(x,{\rm F}_{[x]}),$ 根据唯一分解定理求出对应的多项式$\rm{F}$

$1$ 多点求值

还是分治+构造。

首先一种思维是:用多项式除法来降次

具体来说就是
$$
\rm{F=PQ+R}
$$
这是带余除法的标准式,其中一定保证了$\deg(\rm{R})\leq \deg(\rm{P})$且$\deg(\rm{R})\leq \deg(\rm{Q})$.

所以假设我们令$\rm{P_{[x]}Q_{[x]}}=0$,那么对于同一个$x$就会有$\rm{F_{[x]}=R_{[x]}}$。

所以我们如果想要分治,那么就需要先构造出一个$\rm{Q}$且$\deg(\rm{Q})=\frac{1}{2}\deg(\rm F)$

那么我们直接让$\rm F$对$\rm Q$取模就可以得到$\rm R$,然后不断分治下去就可以$n \log^2 n$计算了。

设第$i$个需要求值的$x$是$A_i$,那么关于F的构造其实很简单,只需要让他满足$\rm Q_{[A_i]}=0$即可,所以完全可以想到构造一个$m$次的多项式$\rm Q$:
$$
\rm Q=\prod(x-A_i)
$$
显然这个东西,他还是可以分治来做,于是多点求值似乎就不能再优化了,因为他复杂度完全平衡了,即预处理复杂度和运算复杂度都是$\log^2$级别的。

哦,然后对于LuoguP5050这道题,卡常十分严重,所以一开始的版本是这个画风的:

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#pragma GCC target("avx")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <ctime>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

#define rr register
#define MAXN 270009
#define LL long long
#define Mod 998244353

using namespace std ;
const LL Gp = 3 ; vector <int> P[MAXN] ;
int N, M, base[MAXN], F[MAXN], gg[20][MAXN], Ls[MAXN], R[MAXN] ;

inline LL expow(LL a, int b){
LL res = 1 ;
while (b){
if (b & 1) (res *= a) %= Mod ;
a = a * a % Mod, b >>= 1 ;
}
return res ;
}
inline void NTT(int *J, const int &L, const int &flag){
rr int m = 0, i ;
for (i = 0 ; i < L ; ++ i)
if (i < R[i]) J[i] ^= J[R[i]] ^= J[i] ^= J[R[i]] ;
for (i = 1 ; i < L ; i <<= 1, ++ m){
rr int *rua = gg[m] ;
for (int j = 0 ; j < L ; j += (i << 1)){
for (int k = 0 ; k < i ; ++ k){
LL real = J[j + k],
iroot = J[j + k + i] * (LL)rua[k] ;
J[j + k] = (real + iroot) % Mod,
J[j + k + i] = ((real - iroot) % Mod +Mod)%Mod;
}
}
}
if (flag > 0) return ;
rr int Inv = expow(L, Mod - 2) ; reverse(J + 1, J + L) ;
for (int i = 0 ; i < L ; ++ i) J[i] = 1ll * J[i] * Inv % Mod ;
}
int X[MAXN], Y[MAXN] ;
void segNTT(int l, int r, int rt){
if (l == r){
Ls[rt] = 1 ;
P[rt].push_back((-base[l]%Mod+Mod)%Mod) ;
P[rt].push_back(1) ;
return ;
}
int i ;
int lc = rt << 1 ;
int rc = rt << 1 | 1 ;
int mid = (l + r) >> 1 ;
segNTT(l, mid, rt << 1) ;
segNTT(mid + 1, r, rt << 1 | 1) ;
Ls[rt] = Ls[rt << 1] + Ls[rt << 1 | 1] ;
int Len = 1, l1 = 0 ; while (Len < ((Ls[rt] + 1) << 1)) Len <<= 1, ++ l1 ;
for (i = 0 ; i < Len ; ++ i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (l1 - 1)) ;
for (i = Ls[lc] + 1 ; i < Len ; ++ i) X[i] = 0 ;
for (i = Ls[rc] + 1 ; i < Len ; ++ i) Y[i] = 0 ;
for (i = 0 ; i <= Ls[lc] ; ++ i) X[i] = P[lc][i] ;
for (i = 0 ; i <= Ls[rc] ; ++ i) Y[i] = P[rc][i] ;
NTT(X, Len, 1), NTT(Y, Len, 1) ;
for (i = 0 ; i < Len ; ++ i) X[i] = (LL)X[i] * (LL)Y[i] % Mod ;
NTT(X, Len, -1) ; for (i = 0 ; i <= Ls[rt] ; ++ i) P[rt].push_back(X[i]) ;
}
int t[MAXN], ig[MAXN] ;
int gt[MAXN], ft[MAXN] ;
void Inv(int *f, int *g, const int &len){
if (len <= 1) {
g[0] = expow(f[0], Mod - 2) ;
return ;
}
int i, l = 0, Len = 1 ;
Inv(f, g, (len + 1) >> 1) ;
while (Len < (len << 1)) Len <<= 1, ++ l ;
for (i = 0 ; i < Len ; ++ i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (l - 1)) ;
for (i = 0 ; i < len ; ++ i) t[i] = f[i] ; NTT(g, Len, 1), NTT(t, Len, 1) ;
for (i = 0 ; i < Len ; ++ i) g[i] = (2ll - (LL)t[i] * (LL)g[i] % Mod + Mod) % Mod * (LL)g[i] % Mod ;
NTT(g, Len, -1) ; for (i = len ; i < Len ; ++ i) g[i] = 0 ;
}
int G[MAXN] ;
inline void _Mod(int *f, vector<int> g, int n, int m, int* Rs){
register int l = 0, O = n - m + 1, L , i ;
for (i = 0 ; i <= (n << 1) ; ++ i) ig[i] = ft[i] = gt[i] = 0 ;
for (i = 0 ; i <= n ; ++ i) ft[i] = f[n - i] ;
for (i = 0 ; i <= m ; ++ i) gt[i] = g[m - i] ; l = 0, L = 1 ;
for (i = O ; i < (n << 1); ++ i) ft[i] = gt[i] = 0 ;
Inv(gt, ig, O) ; while (L < (O << 1)) L <<= 1,++ l ;
for (i = 0 ; i <= L ; ++ i) t[i] = 0 ;
for (i = 0 ; i < L ; ++ i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (l - 1)) ;
NTT(ig, L, 1), NTT(ft, L, 1) ;
for (i = 0 ; i < L ; ++ i) X[i] = 1ll * ft[i] * ig[i] % Mod ;
NTT(X, L, - 1) ; reverse(X, X + O) ; for (i = O ; i < L ; ++ i) X[i] = 0 ;
O = n + 1, L = 1, l = 0 ;
while (L < (O << 1)) L <<= 1, ++ l ;
for (i = 0 ; i < L ; ++ i) G[i] = Y[i] = 0 ;
for (i = 0 ; i <= m ; ++ i) G[i] = g[i] ;
for (i = 0 ; i < L ; ++ i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (l - 1)) ;
NTT(X, L, 1) ; NTT (G, L, 1) ;
for (i = 0 ; i < L ; ++ i) Y[i] = 1ll * G[i] * X[i] % Mod, X[i] = 0 ;
NTT(Y, L, -1) ; for (i = 0 ; i <= m - 1 ; ++ i) Rs[i] = ((1ll * f[i] - Y[i]) + Mod) % Mod ;
}
void cdqNTT(int l, int r, int rt, int *f){
if (l == r) { printf("%d", *f), putchar('\n') ; return ;}
int T[(Ls[rt] + 2) << 1] ;
rr int mid = (l + r) >> 1, i, lc = rt << 1, rc = rt << 1 | 1 ;
_Mod(f, P[lc], Ls[rt] - 1, Ls[lc], T) ; cdqNTT(l, mid, lc, T) ;
_Mod(f, P[rc], Ls[rt] - 1, Ls[rc], T) ; cdqNTT(mid + 1, r, rc, T) ;
}
int main(){
cin >> N >> M ; int i, j ;
for (i = 0 ; i < 19 ;++ i){
int *rua = gg[i] ; rua[0] = 1 ;
int gi = rua[1] = expow(3, 998244352/(1 << (i + 1))) ;
for (j = 2 ; j < (1 << i) ; ++ j) rua[j] = 1ll * rua[j - 1] * gi % Mod ;
}
for (i = 0 ; i <= N ; ++ i) scanf("%d", &F[i]) ;
for (i = 1 ; i <= M ; ++ i) scanf("%d", &base[i]) ;
segNTT(1, M, 1), memset(X, 0, sizeof(X)), memset(Y, 0, sizeof(Y)) ;
if (N >= M) _Mod(F, P[1], N, M, F) ; cdqNTT(1, M, 1, F) ; return 0 ;
}

逼得我差点上指令集

然后发现是这个NTT常数太大了,所以考虑直接边角暴力,区间长度小到一定地步直接暴力秦九韶并且循环展开:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void cdqNTT(int l, int r, int rt, int *f){
if (r - l <= 1024) {
for (int i = l ; i <= r ; ++ i){
LL x = base[i], c1, c2, c3, c4, now = f[r - l] ; b[0] = 1 ;
for (int j = 1 ; j <= 16 ; ++ j) b[j] = b[j - 1] * x % Mod ;
for (int j=r-l-1;j-15>=0;j-=16){
c1=(1ll*now*b[16]+1ll*f[j]*b[15]+1ll*f[j-1]*b[14]+1ll*f[j-2]*b[13])%Mod,
c2=(1ll*f[j-3]*b[12]+1ll*f[j-4]*b[11]+1ll*f[j-5]*b[10]+1ll*f[j-6]*b[9])%Mod,
c3=(1ll*f[j-7]*b[8]+1ll*f[j-8]*b[7]+1ll*f[j-9]*b[6]+1ll*f[j-10]*b[5])%Mod,
c4=(1ll*f[j-11]*b[4]+1ll*f[j-12]*b[3]+1ll*f[j-13]*b[2]+1ll*f[j-14]*b[1])%Mod,
now=(0ll+c1+c2+c3+c4+f[j-15])%Mod;
}
for(int j = (r-l)%16-1 ; j >= 0 ; -- j)now=(1ll*now*x+f[j])%Mod;
printf("%d", now), putchar('\n') ;
}
return ;
}
// if (l == r) { printf("%d", *f), putchar('\n') ; return ;}
int T[(Ls[rt] + 2) << 1] ;
rr int mid = (l + r) >> 1, i, lc = rt << 1, rc = rt << 1 | 1 ;
_Mod(f, P[lc], Ls[rt] - 1, Ls[lc], T) ; cdqNTT(l, mid, lc, T) ;
_Mod(f, P[rc], Ls[rt] - 1, Ls[rc], T) ; cdqNTT(mid + 1, r, rc, T) ;
}

然后就可以随便过了。

$2$ 快速插值

首先思考拉格朗日插值:
$$
\rm{F}=\mathcal{\sum y_i\prod_{i\neq j}\frac{x-x_j}{x_i-x_j}}
$$
我们发现$\prod (x-x_j)$就是个弟弟,于是考虑:
$$
\rm{G}=\mathcal {\sum \frac{y_i}{\prod_{i\neq j}x_i-x_j}}
$$
如果我们随便设一个多项式$ \phi(x)$
$$
\phi=\prod(x-x_i)
$$
那么原式就变成了:
$$
\rm{G}=\mathcal {\sum \frac{y_i}{\frac{\phi(x_i)}{x-x_i}}}
$$
这东西就可以:

就可以!即
$$
\lim _{x \rightarrow a} \frac{f(x)}{g(x)}=\lim _{x \rightarrow a} \frac{f^{\prime}(x)}{g^{\prime}(x)}
$$
由于是形式幂级数之间的运算,于是就可以胡搞,也就是
$$
\frac{\phi(x_i)}{x-x_i}=\phi’(x_i)
$$
显然关于这个$\phi$是可以分治的,分治完求一个导然后再多点求值即可。

回代之后,求个逆就可以求出G,之后接着分治后面的$\prod(x-x_j)$就完了。

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define rr register
#define MAXN 300011
#define LL long long
#define Mod 998244353

using namespace std ; int Len[MAXN], Q[MAXN], R[MAXN] ;
int N, *P[MAXN], *K[MAXN], bx[MAXN], gg[25][MAXN], by[MAXN], cy[MAXN] ;

const int ch_top=4e7+3;
char ch[ch_top],*now_r=ch-1,*now_w=ch-1;

inline int read(){
while(*++now_r<'0');
register int x=*now_r-'0';
while(*++now_r>='0')x=x*10+*now_r-'0';
return x;
}
inline void write(int x){
static char st[20];static int top;
while(st[++top]='0'+x%10,x/=10);
while(*++now_w=st[top],--top);
*++now_w=' ';
}
inline LL expow(int a, int b){
rr LL res = 1 ;
while (b){
if (b & 1)
res = res * 1ll * a % Mod ;
a = 1ll * a * a % Mod, b >>= 1 ;
}
return res ;
}
inline void pre(){
rr int i, j ;
for (i = 0 ; i < 20 ; ++ i){
int *now = gg[i] ; now[0] = 1 ;
int p = now[1] = expow(3, 998244352 / (1 << (i + 1))) ;
for (j = 2 ; j < (1 << i) ; ++ j) now[j] = 1ll * now[j - 1] * p % Mod ; // -1
}
}
void NTT(int *J, int L, int o){
rr int i, j, k, m = 0 ;
for (i = 0 ; i < L ; ++ i) if (i < R[i]) swap(J[R[i]], J[i]) ;
for (i = 1 ; i < L ; i <<= 1, ++ m){
const int *now = gg[m] ;
for (j = 0 ; j < L ; j += (i << 1))
for (k = 0 ; k < i ; ++ k){
const LL x = J[j + k], y = 1ll * now[k] * J[i + j + k] ;
J[j + k] = (x + y) % Mod, J[i + j + k] = ((x - y) % Mod + Mod) % Mod ;
}
}
if (o > 0) return ; const int inv = expow(L, Mod - 2) ;
reverse(J + 1, J + L) ; for (i = 0 ; i < L ; ++ i) J[i] = 1ll * inv * J[i] % Mod ;
}
int ft[MAXN], gt[MAXN], ig[MAXN] ;
int t[MAXN], G[MAXN], X[MAXN], Y[MAXN] ;

void Inv(int *f, int *g, const int &len){
if (len <= 1) {
g[0] = expow(f[0], Mod - 2) ;
return ;
}
rr int i, l = 0, Len = 1 ;
Inv(f, g, (len + 1) >> 1) ;
while (Len < (len << 1)) Len <<= 1, ++ l ;
for (i = 0 ; i < Len ; ++ i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (l - 1)) ;
for (i = 0 ; i < len ; ++ i) t[i] = f[i] ; NTT(g, Len, 1), NTT(t, Len, 1) ;
for (i = 0 ; i < Len ; ++ i) g[i] = (2ll - (LL)t[i] * (LL)g[i] % Mod + Mod) % Mod * (LL)g[i] % Mod ;
NTT(g, Len, -1) ; for (i = len ; i < Len ; ++ i) g[i] = 0 ;
}
void solve(int l, int r, int rt){
if (l == r){
P[rt] = new int[2] ; Len[rt] = 1 ;
P[rt][0] = (-bx[l]+Mod)%Mod , P[rt][1] = 1 ; return ;
}
rr int i ;
int lc = rt << 1 ;
int rc = rt << 1 | 1 ;
int mid = (l + r) >> 1 ;
solve(l, mid, lc), solve(mid + 1, r, rc) ;
Len[rt] = Len[lc] + Len[rc], P[rt] = new int[Len[rt] + 1] ;
rr int L = 1, l1 = 0 ; while (L < ((Len[rt] + 1) << 1)) L <<= 1, ++ l1 ;
for (i = 0 ; i < L ; ++ i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (l1 - 1)) ;
for (i = Len[lc] + 1 ; i < L ; ++ i) X[i] = 0 ;
for (i = Len[rc] + 1 ; i < L ; ++ i) Y[i] = 0 ;
for (i = 0 ; i <= Len[lc] ; ++ i) X[i] = P[lc][i] ;
for (i = 0 ; i <= Len[rc] ; ++ i) Y[i] = P[rc][i] ;
NTT(X, L, 1), NTT(Y, L, 1) ;
for (i = 0 ; i < L ; ++ i) X[i] = 1ll * X[i] * Y[i] % Mod ;
NTT(X, L, -1) ;
for (i = 0 ; i <= Len[rt] ; ++ i) P[rt][i] = X[i] ;
}
void _Dev(int *f, int *g, int len){
rr int i ; g[len] = 0 ;
for(i = 1 ; i <= len ; ++ i) g[i - 1] = 1ll * i * f[i] % Mod ;
}
void _Mod(int *f, int *g, int *res, int n, int m){
int L = 1, l = 0, i, o = n - m + 1, d = n << 1 ;
for (i = 0 ; i < d ; ++ i) ft[i] = gt[i] = ig[i] = 0 ;
for (i = 0 ; i <= n ; ++ i) ft[i] = f[n - i] ;
for (i = 0 ; i <= m ; ++ i) gt[i] = g[m - i] ;
for (i = o ; i < (n << 1) ; ++ i) ft[i] = gt[i] = 0 ; Inv(gt, ig, o) ;
while (L < (o << 1)) L <<= 1, ++ l ;
for (i = 0 ; i < L ; ++ i) t[i] = 0, R[i] = (R[i >> 1] >> 1) | ((i & 1) << (l - 1)) ;//1
NTT(ig, L, 1) ; NTT(ft, L, 1) ;
for (i = 0 ; i < L ; ++ i) X[i] = 1ll * ft[i] * ig[i] % Mod ;
NTT(X, L, -1) ; reverse(X, X + o) ;
for (i = o ; i < L ; ++ i) X[i] = 0 ;
o = n + 1, L = 1, l = 0 ;
while (L < (o << 1)) L <<= 1, ++ l ;
for (i = 0 ; i < L ; ++ i) G[i] = 0 ;
for (i = 0 ; i <= m ; ++ i) G[i] = g[i] ;
for (i = 0 ; i < L ; ++ i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (l - 1)) ;//2
NTT(X, L, 1) ; NTT(G, L, 1) ;
for (i = 0 ; i < L ; ++ i) Y[i] = 1ll * X[i] * G[i] % Mod, X[i] = 0 ;//3
NTT(Y, L, -1) ; for (i = 0 ; i <= m - 1 ; ++ i) res[i] = ((1ll * f[i] - Y[i]) % Mod + Mod) % Mod;
}
LL b[100] ;
void cdqNTT(int l, int r, int rt, int *f){
if (r - l <= 512) {
for (int i = l ; i <= r ; ++ i){
LL x = bx[i], c1, c2, c3, c4, now = f[r - l] ; b[0] = 1 ;
for (int j = 1 ; j <= 16 ; ++ j) b[j] = b[j - 1] * x % Mod ;
for (int j=r-l-1;j-15>=0;j-=16){
c1=(1ll*now*b[16]+1ll*f[j]*b[15]+1ll*f[j-1]*b[14]+1ll*f[j-2]*b[13])%Mod,
c2=(1ll*f[j-3]*b[12]+1ll*f[j-4]*b[11]+1ll*f[j-5]*b[10]+1ll*f[j-6]*b[9])%Mod,
c3=(1ll*f[j-7]*b[8]+1ll*f[j-8]*b[7]+1ll*f[j-9]*b[6]+1ll*f[j-10]*b[5])%Mod,
c4=(1ll*f[j-11]*b[4]+1ll*f[j-12]*b[3]+1ll*f[j-13]*b[2]+1ll*f[j-14]*b[1])%Mod,
now=(0ll+c1+c2+c3+c4+f[j-15])%Mod;
}
for(int j = (r-l)%16-1 ; j >= 0 ; -- j)now=(1ll*now*x+f[j])%Mod;
cy[i] = now ;
}
return ;
}
// if (l == r) { printf("%d", *f), putchar('\n') ; return ;}
int T[(Len[rt] + 2) << 1] ;
rr int mid = (l + r) >> 1, i, lc = rt << 1, rc = rt << 1 | 1 ;
_Mod(f, P[lc], T, Len[rt] - 1, Len[lc]) ; cdqNTT(l, mid, lc, T) ;
_Mod(f, P[rc], T, Len[rt] - 1, Len[rc]) ; cdqNTT(mid + 1, r, rc, T) ;
}
/*
void cdqNTT(int l, int r, int rt, int *f){
int T[(Len[rt] + 2) << 1] ;
if (l == r) { cy[l] = f[0] ; return ; }
int mid = (l + r) >> 1, lc = rt << 1, rc = lc | 1 ;
_Mod(f, P[lc], T, Len[rt] - 1, Len[lc]), cdqNTT(l, mid, lc, T) ;
_Mod(f, P[rc], T, Len[rt] - 1, Len[rc]), cdqNTT(mid + 1, r, rc, T) ;
}*/
void cdqLg(int l, int r, int rt){
if (l == r){
K[rt] = new int[2] ;
K[rt][0] = 1ll * by[l] * expow(cy[l], Mod - 2) % Mod ;
K[rt][1] = 0 ; return ;
}
static int A[MAXN], B[MAXN], C[MAXN], D[MAXN] ;
rr int mid = (l + r) >> 1, lc = rt << 1, rc = lc | 1, i ;
cdqLg(l, mid, lc), cdqLg(mid + 1, r, rc) ; int L = 1, l0 = 0 ;
while (L < ((Len[rt] + 1) << 1)) L <<= 1, ++ l0 ;
for (i = 0 ; i < L ; ++ i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (l0 - 1)) ;
for (i = Len[lc] + 1 ; i < L ; ++ i) A[i] = C[i] = 0 ;
for (i = Len[rc] + 1 ; i < L ; ++ i) B[i] = D[i] = 0 ;
for (i = 0 ; i <= Len[lc] ; ++ i) A[i] = K[lc][i], C[i] = P[lc][i] ;
for (i = 0 ; i <= Len[rc] ; ++ i) B[i] = K[rc][i], D[i] = P[rc][i] ;
NTT(A, L, 1), NTT(B, L, 1), NTT(C, L, 1), NTT(D, L, 1) ;
for (i = 0 ; i < L ; ++ i) A[i] = (1ll * A[i] * D[i] % Mod + 1ll * B[i] * C[i] % Mod) % Mod ;
NTT(A, L, -1) ; K[rt] = new int[Len[rt] + 1] ; for(i = 0 ; i <= Len[rt] ; ++ i ) K[rt][i] = A[i] ;
}
int main(){
// rr int W ; freopen("2.in", "r", stdin) ;
fread(ch,1,ch_top,stdin);
N = read() ; int i ; pre() ;
for (i = 1 ; i <= N ; ++ i) bx[i] = read(), by[i] = read() ;
solve(1, N, 1) ; memset(X, 0, sizeof(X)) ; memset(Y, 0, sizeof(Y));
_Dev(P[1], Q, Len[1]) ; cdqNTT(1, N, 1, Q) ; cdqLg(1, N, 1) ;
// for (i = 0 ; i < N ; ++ i) cout << K[1][i] << " " ;
for (i = 0 ; i < N ; ++ i) write(K[1][i]) ; fwrite(ch,1,now_w-ch,stdout) ; return 0 ;
}

总结:すべて分割べることのできる多項式生活最高だ!(一切皆可分治的多项式生活赛高!)