多项式相关

2026-02-05T15:59:56+08:00 | 6分钟阅读 | 更新于 2026-02-05T15:59:56+08:00

@ Jason Chan

史铁生同机位。

规定

对多项式 $f(x)$ 提取 $x^n$ 项系数记作 $[x^n]f(x)$，也可以记作 $f_n$。

前置知识

泰勒展开

$f(x)$ 在 $x_0$ 处的展开为：

$$f(x)=\sum\limits_{i=0}^\infty \dfrac{f^{(i)}(x_0)}{i!}(x-x_0)^i$$

麦克劳林展开 是 $x_0=0$ 的特例，有简洁形式：

$$f(x)=\sum\limits_{i=0}^\infty \dfrac{f^{(i)}(0)}{i!}x^i$$

多项式微积分

不严格区分求导与微分。

微分

$$F’(x)=\sum\limits_{i=0}(i+1)F_{i+1}x^i$$

积分

$$\int F(x)\mathrm dx=\sum\limits_{i=1}\dfrac{F_{i-1}}{i}x^i$$

牛顿迭代法

已知 $G$，若 $G(F(x))=0\pmod {x^n}$，求 $F$。

结论：设 $F_0(x)$ 表示 $\bmod {x^{\frac n2}}$ 下的结果，那么有：$F(x)\equiv F_0(x)-G(F_0(x))\cdot\dfrac{\mathrm dF_0(x)}{\mathrm{d}G(F_0(x))}$，这里写 $\dfrac{\mathrm dy}{\mathrm dx}$ 是突出表示对 $F(x)$ 求导。

证明：考虑 $G(F(x))$ 在 $F_0(x)$ 处的泰勒展开，$G(F(x))=\sum\limits_{i=0}^\infty\dfrac{G^{(i)}(F_0(x))}{i!}(F(x)-F_0(x))^i$，由于 $F(x)-F_0(x)$ 的最低项为 $x^{\frac n2}$，故平方下最低项为 $x^n$，而我们求的是 ${}\bmod {x^n}$ 下的结果，所以再往后都是 $0$。即 $G(F(x))=G(F_0(x))+G’(F_0(x))(F(x)-F_0(x))\pmod {x^n}$。令 $G(F(x))\equiv 0\pmod {x^n}$，于是得到上述结果。

多项式运算

乘法

不讲了。

除法

给出 $F(x)$，求使得 $G(x)\cdot F(x)\equiv 1\pmod {x^n}$ 的 $G(x)$。

当 $n=0$ 时显然是求一下逆元，考虑看看能不能倍增。

假设已经求得 $G_0(x)\cdot F(x)\equiv 1\pmod x^{\frac n2}$，显然有 $G_0(x)\equiv G(x)\pmod {x^{\frac n2}}$。

$$ \begin{aligned} G_0(x)-G(x)&\equiv 0\pmod{x^{\frac n2}}\\ G_0^2(x)-2G_0(x)\cdot G(x)+G^2(x)&\equiv 0\pmod{x^n} \\ G_0^2(x)\cdot F(x)-2G_0(x)\cdot G(x)\cdot F(x)+G^2(x)\cdot F(x)&\equiv 0\pmod{x^n} \\ F(x)\cdot G^2_0(x)-2G_0(x)+G(x)&\equiv 0\pmod {x^n}\\ G(x)&\equiv 2G_0(x)-F(x)\cdot G_0^2(x)\pmod {x^n} \end{aligned} $$

于是可以倍增求解。

开方

给出 $A$，求 $B$ 使得 $B^2\equiv A\pmod {x^n}$。

设 $F(B(x))=B^2(x)-A(x)$，于是 $F’(B(x))=2B(x)$

$$ \begin{aligned} B(x) &\equiv B_0(x)-\dfrac{F(B_0(x))}{F’(B_0(x))} \pmod{x^n}\\ &\equiv B_0(x)-\dfrac{B_0^2(x)-A(x)}{2B_0(x)} \pmod{x^n} \\ &\equiv \dfrac{A(x)+B^2_0(x)}{2B_0(x)} \pmod{x^n} \end{aligned} $$

然后对于 $0$ 次项直接求二次剩余，我不会二次剩余所以只能 bsgs，索性模板题

带余除法

给出 $n$ 次多项式 $F$ 以及 $m$ 次多项式 $G\quad(n\ge m)$，求 $n-m$ 次多项式 $Q$ 以及小于 $m$ 次的多项式 $R$ 使得 $F=G\cdot Q+R$。

对于 $n$ 次多项式 $F$，设 $F_R(x)=x^nF\left(\dfrac {1}x\right)$，即将 $i$ 次与 $n-i+1$ 次系数互换后的结果。

推式子：

$$ \begin{aligned} F(x)&=G(x)\cdot Q(x)+R(x)\\ F\left(\dfrac{1}{x}\right)&=G\left(\dfrac{1}{x}\right)\cdot Q\left(\dfrac{1}{x}\right)+Q\left(\dfrac{1}{x}\right)\\ x^nF\left(\dfrac{1}{x}\right)&=x^{m}G\left(\dfrac{1}{x}\right)\cdot x^{n-m}Q\left(\dfrac{1}{x}\right)+x^{n}Q\left(\dfrac{1}{x}\right)\\ F_R(x)&=G_R(x)\cdot Q_R(x)+x^{n-m+1}Q(\dfrac 1x) \\ F_R(x)&\equiv G_R(x)\cdot Q_R(x)\pmod{x^{n-m+1}} \end{aligned} $$

于是就得到 $Q_R(x)\equiv \dfrac{F_R(x)}{G_R(x)}\pmod{x^{n-m+1}}$，多项式求逆再反转一下即可，最后乘上 $G$ 被 $F$ 减一下就得到了 $R$。

多项式 $\ln,\exp$

由麦克劳林级数定义：

$$\ln F(x)=-\sum\limits_{i=1}\dfrac{(1-F(x))^i}{i}$$ $$\exp F(x)=\sum\limits_{i=0}\dfrac{F(x)^i}{i!}$$

求 $\ln F(x)$

直接从定义求复杂度太劣了，考虑求导。

设 $\ln F(x)\equiv G(x)\pmod{x^n}$，则

$$ \begin{aligned} \dfrac{\mathrm d }{\mathrm dx}\ln F(x)&\equiv \dfrac{\mathrm d }{\mathrm dx}G(x)\\ \dfrac{\mathrm d }{\mathrm dF(x)}\dfrac{\mathrm d F(x)}{\mathrm dx}\ln F(x)&\equiv\dfrac{\mathrm d }{\mathrm dx}G(x)\\ \dfrac{F’(x)}{F(x)}&\equiv G’(x)\\ G(x)&\equiv \int\dfrac{F’(x)}{F(x)}\mathrm dx \end{aligned} $$

于是先求导，再求逆，再积分即可。

求 $\exp F(x)$

考虑大力牛迭。

设 $G(x)=\exp F(x)$，那么 $\ln G(x)-F(x)=0$，设 $H(G(x))=\ln G(x)-F(x)=0$。

$$ \begin{aligned} G(x)&\equiv G_0(x)-\dfrac{\ln G_0(x)-F(x)}{\frac{1}{G_0(x)}}\\ &\equiv G_0(x)-G_0(x)(\ln G_0(x)-F(x))\\ &\equiv G_0(x)\cdot(1+F(x)-\ln G_0(x))\pmod{x^n} \end{aligned} $$

显然，只有在 $F_0=0$ 的时候才能这样做。

多项式快速幂

注意到 $F_0=1$，因此 $\ln$ 下麦克劳林展开后的常数项始终为 $0$，进而可以进行 $\exp$ 操作。

$$F^k(x)=\exp (k\cdot\ln F(x))$$

当 $F_0\neq 1$ 时？一种简单的想法是先将 $F(x)$ 数乘 $F_0^{-1}$，但是没考虑到 $F_0=0$ 的情况。考虑找到 $F(x)$ 的最低非零次项 $f_tx^t$，然后整体除以 $(f_tx^t)^k$，然后还是一样的。注意这个 $kt$ 如果不小于 $n$ 了那么答案全是零，此外在模 $P$ 意义下，$k$ 应该模 $P-1$，这是费马小定理。

集大成者

Code

  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
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260


#include <cmath>
#include <vector>
#include <iostream>
#include <unordered_map>

using ll = long long;
using ull = unsigned long long;

using namespace std;

const int N = 2.6e6 + 10;
const ll P = 998244353;
const ll GG = 114514;
const int inv2 = 499122177;

int rev[N], n, m;

void pret (int& n) {
    int k = 1;
    while (k <= n) k <<= 1;
    n = k;
    for (int i = 0; i < n; i ++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? n >> 1 : 0);
}

ll qpow (ll base, int k) {
    ll res = 1;
    while (k) {
        if (k & 1) res = res * base % P;
        base = base * base % P;
        k >>= 1;
    }
    return res;
} 

const ll invGG = qpow (GG, P - 2);

void NTT (int* g, bool flag, int n) {
    static ull f[N], w[N];
    for (int i = 0; i < n; i ++) f[i] = g[ rev[i] ];
    w[0] = 1;
    for (int l = 1; l < n; l <<= 1) {
        ull G = qpow (flag ? GG : invGG, (P - 1) / (l << 1));
        for (int i = 1; i < l; i ++) w[i] = w[i - 1] * G % P;
        for (int k = 0; k < n; k += (l << 1)) 
            for (int p = 0; p < l; p ++) {
                int t = w[p] * f[k | p | l] % P;
                f[k | p | l] = f[k | p] + P - t;
                f[k | p] += t;
            }
        if (l == (1 << 17)) for (int i = 0; i < n; i ++) f[i] %= P;
    }
    if (!flag) {
        ull invn = qpow (n, P - 2);
        for (int i = 0; i < n; i ++) g[i] = f[i] % P * invn % P;
    } else for (int i = 0; i < n; i ++) g[i] = f[i] % P;
}

vector <int> f, g;

vector <int> operator + (const vector <int>& x, const vector <int>& y) {
    int l = max ( x.size (), y.size () );
    vector <int> ans(l);
    for (int i = 0; i < l; i ++) {
        int v1 = (i < x.size ()) ? x[i] : 0;
        int v2 = (i < y.size ()) ? y[i] : 0;
        ans[i] = (v1 + v2) % P;
    }
    while (ans.size () && !ans.back ()) ans.pop_back ();
    return ans;
}

vector <int> operator - (const vector <int>& x, const vector <int>& y) {
    int l = max ( x.size (), y.size () );
    vector <int> ans (l);
    for (int i = 0; i < l; i ++) {
        int v1 = (i < x.size ()) ? x[i] : 0;
        int v2 = (i < y.size ()) ? y[i] : 0;
        ans[i] = (v1 - v2 + P) % P;
    }
    while (ans.size () && !ans.back ()) ans.pop_back ();
    return ans;
}

vector <int> operator * (const vector <int>& x, const vector <int>& y) {
    static int f[N], g[N];
    int n = x.size () - 1, m = y.size () - 1;
    m += n; pret (n = m);
    for (int i = 0; i <= n; i ++) f[i] = g[i] = 0;
    for (int i = 0; i < x.size (); i ++) f[i] = x[i];
    for (int i = 0; i < y.size (); i ++) g[i] = y[i];
    NTT (f, 1, n); NTT (g, 1, n);
    for (int i = 0; i <= n; i ++) f[i] = f[i] * 1ll * g[i] % P;
    NTT (f, 0, n);
    vector <int> ans (m + 1);
    for (int i = 0; i <= m; i ++) ans[i] = f[i]; 
    return ans;
}

vector <int> operator * (int coef, const vector <int>& x) {
    auto res = x;
    for (auto& tmp : res) tmp = tmp * 1ll * coef % P;
    return res; 
} 

vector <int> inv (const vector <int>& f) {
    int n = f.size ();
    if (n == 0) return {};
    vector <int> g = { (int)qpow (f[0], P - 2) };
    int len = 1;
    while (len < n) {
        len <<= 1;
        vector <int> bt (len);
        for(int i = 0; i < len && i < f.size (); i ++) bt[i] = f[i];
        vector <int> term = bt * (g * g); 
        if (term.size () > len) term.resize (len);
        g = 2 * g - term;
        if (g.size () > len) g.resize (len);
    }
    
    g.resize (n);
    return g;
}

vector <int> Integral (vector <int> f) {
    f.push_back (0); int n = f.size ();
    for (int i = n - 1; i; i --) f[i] = f[i - 1] * 1ll * qpow (i, P - 2) % P;
    f[0] = 0;
    return f;
}

vector <int> Derivative (vector <int> f) {
    int n = f.size ();
    if (n == 1) return {0};
    for (int i = 0; i < n - 1; i ++) f[i] = f[i + 1] * 1ll * (i + 1) % P;
    f.resize (n - 1);
    return f;
}

int bsgs (int n) {
    if (n == 0) return 0;
    unordered_map <int, int> mp;
    int m = ceil (sqrt (P - 1));
    ll base = 1;
    ll cur = n;
    for (int j = 0; j < m; j ++) {
        mp[cur] = j;
        cur = cur * GG % P;
    }
    ll step = qpow (GG, m), now = 1;
    for (int i = 1; i <= m; i ++) {
        now = now * step % P;
        if (mp.count (now)) {
            ll K = i * 1ll * m - mp[now];
            K = (K % (P - 1) + (P - 1)) % (P - 1);
            if (K % 2 != 0) return -1; 
            ll x = qpow (GG, K / 2);
            return min (1ll * x, P - x); 
        }
    }
    return -1;
}

vector <int> sqrt (const vector <int>& f) {
    int n = f.size (), len = 1;
    vector <int> g = {bsgs (f[0])};
    while (g.size () < n) {
        len <<= 1;
        vector <int> ff (len);
        g.resize (len);
        for (int i = 0; i < len && i < n; i ++) ff[i] = f[i];
        auto prod = ff * inv (g); prod.resize (len);
        g = inv2 * (g + prod);
    }
    g.resize (n);
    return g;
}

vector <int> revPoly (const vector <int>& f) {
    auto g = f; int sz = g.size ();
    for (int i = 0; i < sz / 2; i ++) swap (g[i], g[sz - i - 1]);
    return g;
}

pair < vector <int>, vector <int> > divide (const vector <int>& f, const vector <int>& g) {
    int n = f.size () - 1, m = g.size () - 1;
    if (n < m) return { vector <int> (0), f };
    auto rF = revPoly (f), rG = revPoly (g); rG.resize (n - m + 1); rF.resize (n - m + 1); 
    auto rQ = rF * inv (rG); rQ.resize (n - m + 1); 
    auto Q = revPoly (rQ); 
    auto R = f - g * Q; R.resize (m);
    while (!R.empty () && !R.back ()) R.pop_back ();
    return {Q, R};
}

vector <int> ln (const vector <int>& f) {
    int n = f.size ();
    auto dF = Derivative (f);
    auto q = dF * inv (f); 
    auto res = Integral (q); res.resize (n);
    return res;
}

vector <int> exp (const vector <int>& f) {
    if (f.size () == 1) return {1};
    vector <int> g, base = {1}; g = {1};
    int len = 1, n = f.size ();
    while (len < n) {
        len <<= 1;
        g.resize (len);
        auto lng = ln (g);
        g = g * (base + f - lng);
    }
    g.resize (n);
    return g;
}

vector <int> power (const vector <int>& f, ll k1, ll k2, ll k3) {
    int n = f.size ();
    int lw = 0;
    while (lw < n && !f[lw]) lw ++;
    if (lw == n) return vector <int> (n, 0);
    if (k3 == 0) { vector<int> res(n, 0); res[0] = 1; return res; }
    if (lw * 1ll * k3 >= n) return vector <int> (n, 0);
    vector <int> g;
    for (int i = lw; i < n; i ++) g.push_back (f[i]);
    g.resize (n - lw * k3); 
    int c = g[0];
    int inc = qpow(c, P - 2);
    for (auto& x : g) x = 1ll * x * inc % P;
    g = qpow (c, k2) * exp (k1 * ln (g));
    vector <int> ans (n, 0);
    int fuckyou = lw * k3;
    for (int i = 0; i < g.size (); i ++) ans[i + fuckyou] = g[i];
    return ans;
}

char st[N];

int main (void) {
    
    scanf ("%d%s", &n, st + 1); n --;
    f.resize (n + 1); 
    for (int& x : f) scanf ("%d", &x);
    
    ll k1 = 0, k2 = 0, k3 = 0;
    for (int i = 1; st[i]; i ++) {
        int d = st[i] - '0';
        k1 = (k1 * 10 + d) % P;
        k2 = (k2 * 10 + d) % (P - 1);
        if (k3 < n) k3 = k3 * 10 + d; 
    }
    
    auto ans = power (f, k1, k2, k3);
    
    for (auto& x : ans) printf ("%d ", x);
    puts ("");
    
    return 0;
}