概述
【模板】多项式除法
题目链接：luogu P4512
题目大意
给你一个 n 次多项式 F(x) 和 m 次多项式 G(x)，要你求出多项式 Q(x),R(x) 使得 Q(x) 为 n-m 次多项式，R(x) 项数小于 m，然后 F(x)=Q(x)*G(x)+R(x)。
思路
考虑到如果没有余数就是直接多项式求逆，但是有余数，所以问题就在于怎么把余数消掉。
那我们一般的取模是消掉高项的，但是余数是低项的，所以我们考虑一个操作叫做翻转，然后有一个这样的定义方法：
F
T
(
x
)
=
x
n
F
(
x
−
1
)
F^T(x)=x^nF(x^{-1})
FT(x)=xnF(x−1)
其实挺显然的，就原本在
x
i
x^i
xi 的变成了
x
n
−
i
x^{n-i}
xn−i。
然后考虑推给的式子：
F
(
x
)
=
Q
(
x
)
∗
G
(
x
)
+
R
(
x
)
F(x)=Q(x)*G(x)+R(x)
F(x)=Q(x)∗G(x)+R(x)
然后换元：
F
(
x
−
1
)
=
Q
(
x
−
1
)
∗
G
(
x
−
1
)
+
R
(
x
−
1
)
F(x^{-1})=Q(x^{-1})*G(x^{-1})+R(x^{-1})
F(x−1)=Q(x−1)∗G(x−1)+R(x−1)
集体乘
x
n
x^n
xn：
x
n
F
(
x
−
1
)
=
x
n
Q
(
x
−
1
)
∗
G
(
x
−
1
)
+
x
n
R
(
x
−
1
)
x^nF(x^{-1})=x^nQ(x^{-1})*G(x^{-1})+x^nR(x^{-1})
xnF(x−1)=xnQ(x−1)∗G(x−1)+xnR(x−1)
然后你可以看这几个多项式的项数分别是多少：
F
(
x
)
F(x)
F(x)：
n
n
n，
G
(
x
)
G(x)
G(x)：
m
m
m，
Q
(
x
)
Q(x)
Q(x)：
n
−
m
n-m
n−m，
R
(
x
)
R(x)
R(x)：
m
−
1
m-1
m−1
x
n
F
(
x
−
1
)
=
x
n
−
m
Q
(
x
−
1
)
∗
x
m
G
(
x
−
1
)
+
x
n
−
m
+
1
∗
x
m
−
1
R
(
x
−
1
)
x^nF(x^{-1})=x^{n-m}Q(x^{-1})*x^mG(x^{-1})+x^{n-m+1}*x^{m-1}R(x^{-1})
xnF(x−1)=xn−mQ(x−1)∗xmG(x−1)+xn−m+1∗xm−1R(x−1)
F
T
(
x
)
=
Q
T
(
x
)
∗
G
T
(
x
)
+
x
n
−
m
+
1
R
T
(
x
)
F^T(x)=Q^T(x)*G^T(x)+x^{n-m+1}R^T(x)
FT(x)=QT(x)∗GT(x)+xn−m+1RT(x)
然后你会发现它（
R
T
(
x
)
R^T(x)
RT(x)）变成了高项的，然后你可以在
(
m
o
d
x
n
−
m
+
1
)
{pmod {x^{n-m+1}}}
(modxn−m+1) 的条件下进行。
F
T
(
x
)
=
Q
T
(
x
)
∗
G
T
(
x
)
(
m
o
d
x
n
−
m
+
1
)
F^T(x)=Q^T(x)*G^T(x)pmod{x^{n-m+1}}
FT(x)=QT(x)∗GT(x)(modxn−m+1)
然后后面的操作都能看出了：
Q
T
(
x
)
=
F
T
(
x
)
∗
G
T
(
x
)
−
1
(
m
o
d
x
n
−
m
+
1
)
Q^T(x)=F^T(x)*G^T(x)^{-1}pmod{x^{n-m+1}}
QT(x)=FT(x)∗GT(x)−1(modxn−m+1)
那就可以做了，先得到翻转的
F
T
,
G
T
F^T,G^T
FT,GT。
然后
G
T
G^T
GT 逆元求出来，然后乘起来就是答案啦。
然后通过
F
(
x
)
=
Q
(
x
)
∗
G
(
x
)
+
R
(
x
)
F(x)=Q(x)*G(x)+R(x)
F(x)=Q(x)∗G(x)+R(x) 有
R
(
x
)
=
F
(
x
)
−
Q
(
x
)
∗
G
(
x
)
R(x)=F(x)-Q(x)*G(x)
R(x)=F(x)−Q(x)∗G(x)，所以乘一下减一下就有了。
然后要小小注意的是范围要注意一下，因为你有取模所以你要把以外的都直接清空掉。
然后就没什么了。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define mo 998244353
#define clr(f, n) memset(f, 0, (n) * sizeof(int))
#define cpy(f, g, n) memcpy(f, g, (n) * sizeof(int))
using namespace std;
const int N = 100000 * 8 + 1;
int n, m, f[N], g[N], an[N], inv[N], G = 3, Gv;
int jia(int x, int y) {return x + y >= mo ? x + y - mo : x + y;}
int jian(int x, int y) {return x < y ? x - y + mo : x - y;}
int cheng(int x, int y) {return 1ll * x * y % mo;}
int ksm(int x, int y) {int re = 1; while (y) {if (y & 1) re = cheng(re, x); x = cheng(x, x); y >>= 1;} return re;}
void Init() {
Gv = ksm(G, mo - 2);
inv[0] = inv[1] = 1; for (int i = 2; i < N; i++) inv[i] = cheng(inv[mo % i], mo - mo / i);
}
void get_an(int limit, int l_size) {
for (int i = 0; i < limit; i++)
an[i] = (an[i >> 1] >> 1) | ((i & 1) << (l_size - 1));
}
void NTT(int *f, int limit, int op) {
for (int i = 0; i < limit; i++) if (an[i] < i) swap(f[an[i]], f[i]);
for (int mid = 1; mid < limit; mid <<= 1) {
int Wn = ksm(op == 1 ? G : Gv, (mo - 1) / (mid << 1));
for (int R = (mid << 1), j = 0; j < limit; j += R) {
int w = 1;
for (int k = 0; k < mid; k++, w = cheng(w, Wn)) {
int x = f[j | k], y = cheng(w, f[j | mid | k]);
f[j | k] = jia(x, y); f[j | mid | k] = jian(x, y);
}
}
}
if (op == -1) {
int limv = ksm(limit, mo - 2);
for (int i = 0; i < limit; i++) f[i] = cheng(f[i], limv);
}
}
void px(int *f, int *g, int limit) {
for (int i = 0; i < limit; i++)
f[i] = cheng(f[i], g[i]);
}
void times(int *f, int *g, int n, int m) {
static int tmp[N];
int limit = 1, l_size = 0; while (limit <= n + n) limit <<= 1, l_size++;
cpy(tmp, g, n); clr(tmp + n, limit - n);
get_an(limit, l_size);
NTT(f, limit, 1); NTT(tmp, limit, 1);
px(f, tmp, limit); NTT(f, limit, -1);
clr(f + m, limit - m); clr(tmp, limit);
}
void invp(int *f, int n) {
static int w[N], r[N], tmp[N];
w[0] = ksm(f[0], mo - 2);
int limit = 1, l_size = 0;
for (int len = 2; (len >> 1) <= n; len <<= 1) {
limit = len; l_size++; get_an(limit, l_size);
cpy(r, w, len >> 1);
cpy(tmp, f, limit); NTT(tmp, limit, 1);
NTT(r, limit, 1); px(r, tmp, limit);
NTT(r, limit, -1); clr(r, limit >> 1);
cpy(tmp, w, len); NTT(tmp, limit, 1);
NTT(r, limit, 1); px(r, tmp, limit);
NTT(r, limit, -1);
for (int i = (len >> 1); i < len; i++)
w[i] = jian(cheng(w[i], 2), r[i]);
}
cpy(f, w, n); clr(w, n); clr(r, n); clr(tmp, n);
}
void dao(int *f, int n) {
for (int i = 1; i < n; i++)
f[i - 1] = cheng(f[i], i);
f[n - 1] = 0;
}
void jifen(int *f, int n) {
for (int i = n; i >= 1; i--)
f[i] = cheng(f[i - 1], inv[i]);
f[0] = 0;
}
void lnp(int *f, int n) {
static int g[N];
cpy(g, f, n); dao(g, n);
invp(f, n); times(f, g, n, n);
jifen(f, n - 1); clr(g, n);
}
void mof(int *f, int n, int *g, int m) {
static int f_[N], g_[N];
int L = n - m + 1;
reverse(f, f + n); cpy(f_, f, L); reverse(f, f + n);
reverse(g, g + m); cpy(g_ , g, L); reverse(g, g + m);
invp(g_, L); times(g_, f_, L, L); reverse(g_, g_ + L);
times(g, g_, n, n);
for (int i = 0; i < m - 1; i++) g[i] = jian(f[i], g[i]);
clr(g + m - 1, L);
cpy(f, g_, L); clr(f + L, n - L);
}
int main() {
Init();
scanf("%d %d", &n, &m); n++; m++;
for (int i = 0; i < n; i++) scanf("%d", &f[i]);
for (int i = 0; i < m; i++) scanf("%d", &g[i]);
mof(f, n, g, m);
for (int i = 0; i < n - m + 1; i++) printf("%d ", f[i]); printf("n");
for (int i = 0; i < m - 1; i++) printf("%d ", g[i]);
return 0;
}
最后
以上就是舒心摩托为你收集整理的【luogu P4512】【模板】多项式除法【模板】多项式除法的全部内容，希望文章能够帮你解决【luogu P4512】【模板】多项式除法【模板】多项式除法所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
![洛谷.4512.[模板]多项式除法(NTT)](/uploads/reation/bcimg4.png)
发表评论 取消回复