多项式带余除法+老年选手的多项式瞎吹

解决一类
$$
G=F\cdot P+R ~(\bmod~x^n)
$$
其中$F, G$给定,求解$P$和$R$

$1$

这就很苟,最近要被多项式除法给整疯了,原因大概是我换一道模板就需要换一种写法……原来那种怎么改都不对就很智障……

然后划式子过程就很苟,是一种诡异的构造方式,前置芝士大概是$F(\frac{1}{x})=F^T(x)$,其中$T$表示转置——当然是一个不严谨的记号,意思就是把这个形式幂级数的系数reverse掉。

以下是过程:
$$
\begin{aligned}
G(x)&=F(x)P(x)+R(x)\\
G(\frac{1}{x})&=F(\frac{1}{x})P(\frac{1}{x})+R(\frac{1}{x})\\
\because A_r&= x^nA(\frac{1}{x})\\
\therefore x^nG(\frac{1}{x})&=x^nF(\frac{1}{x})P(\frac{1}{x})+x^nR(\frac{1}{x})\\
\Longrightarrow x^nG(\frac{1}{x})&=x^mF(\frac{1}{x})\cdot x^{n-m}P(\frac{1}{x})+x^{m-1}\cdot x^{n-m+1}R(x)\\
\Longrightarrow G_r(x)&=F_r(x)\cdot P_r(x)+x^{n-m+1}R_r(x)\\
\Longrightarrow G_r(x)&=F_r(x)\cdot P_r(x)+x^{n-m+1}R_r(x) ~(\bmod x^{n-m+1})\\
\Longrightarrow P_r(x)&=F_r(x)\cdot G_r^{-1}(x)~(\bmod x^{n-m+1})\\
\end{aligned}
$$
之后求出$P_r$之后就可以回代原式:
$$
\begin{aligned}
G=F\cdot P+R\\
R = G - F\cdot P
\end{aligned}
$$
于是就完了

$2$

但是实际写法有些问题,比如板子P4512 【模板】多项式除法

这其实就直接做就好,不是很需要考虑清零什么的。但是我总觉得在Inv之后是不是需要重新算一下R……不清楚诶。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
LL Ft[MAXN], Gt[MAXN], IG[MAXN] ;
void _Div(){
int l = 0, O = N - M + 1 ;
reverse(Ft, Ft + N), reverse(Gt, Gt + M) ;
l = 0, L = 1 ; while (L < (O << 1)) L <<= 1, ++ l ;
for (int i = O ; i < N ; ++ i) Ft[i] = Gt[i] = 0 ;
for (int i = 0 ; i < L ; ++ i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (l - 1)) ;
_Inv(Gt, IG, O), NTT(IG, L, 1), NTT(Ft, L, 1) ;
for (int i = 0 ; i < L ; ++ i) P[i] = Ft[i] * IG[i] % Mod ; NTT(P, L, - 1) ; reverse(P, P + O) ;
for (int i = 0 ; i < O ; ++ i) printf("%lld ", P[i]) ; for (int i = O ; i < N ; ++ i) P[i] = 0 ;
O = N, L = 1, l = 0 ; while (L < (O << 1)) L <<= 1, ++ l ;
for (int i = 0 ; i < L ; ++ i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (l - 1)) ;
NTT(P, L, 1), NTT(G, L, 1) ; for (int i = 0 ; i < L ; ++ i) Q[i] = (P[i] * G[i]) % Mod ; NTT(Q, L, -1) ;
}
int main(){
cin >> N >> M, ++ N, ++ M ; int i ;
for (i = 0 ; i < N ; ++ i) scanf("%lld", &F[i]), Ft[i] = F[i] ;
for (i = 0 ; i < M ; ++ i) scanf("%lld", &G[i]), Gt[i] = G[i] ; _Div() ;
puts("") ; for (i = 0 ; i < M - 1 ; ++ i) printf("%lld ", (F[i] - Q[i] + Mod) % Mod) ;
}

但是之后线性递推时需要进行的取模操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void _Div(LL *f, int Len){
int L1 = (K << 1), D, i ;
while (!f[-- L1]) ; if (L1 < K) return ;
for (i = 0 ; i < Len ; ++ i) Ft[i] = 0 ;
for (i = 0 ; i <= L1 ; ++ i) Ft[i] = f[i] ; reverse(Ft, Ft + L1 + 1) ;
for (D = L1 - K + 1, i = D ; i <= L1 ; ++ i) Ft[i] = 0 ; NTT(Ft, Len, 1) ;
for (i = 0 ; i < Len ; ++ i) P[i] = Ft[i] * IG[i] % Mod ; NTT(P, Len, - 1) ;
for (i = D ; i <= L1 ; ++ i) P[i] = 0 ; reverse(P, P + D) ; NTT(P, Len, 1) ;
for (i = 0 ; i < Len ; ++ i) Q[i] = (P[i] * G[i]) % Mod ; NTT(Q, Len, -1) ;
for (i = 0 ; i < K ; ++ i) f[i] = (f[i] - Q[i] + Mod) % Mod ; for (i = K ; i <= L1 ; ++ i) f[i] = 0 ;
}
//main_function
for (i = 1 ; i <= K ; ++ i) G[K - i] = Mod - p[i] ;
for (i = 0 ; i <= K ; ++ i) Gt[i] = G[i] ; reverse(Gt, Gt + K + 1) ;
NTT(G, Len, 1) ; _Inv(Gt, IG, Len >> 1), NTT(IG, Len, 1) ;
for (i = 0 ; i < Len ; ++ i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (l - 1)) ;

看上去很正常,只是多了几个预处理而已。但是不知为何当时写的就很迷。。。并且从这个板子开始我明白了,多项式长度+是否清空这个组合绝对是多项式入门里面最难受的细节。

之后就更迷了,多点求值这玩意儿实在毒瘤:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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 ;
}

这就很烦……鬼知道你tm什么时候忘清空或者忘开long long了就要调一年……艹

$3$

最后趁机说一下写多项式的心得其实就是瞎吹

  • 好烦啊(
  • 代码好长啊(
  • 为什么踏马每次徒手写NTT都会挂啊(
  • 学了半天原来FFT是最没用的啊(
  • 调死我了啊
  • 还不如直接照着模板背呢,每天早读背一发,那个什么教辅不是说来着?“背虽传统,也最实用”(
  • 卧槽每次写一道板子就要交上一整页,我不要面子的吗

正经一点的话,大概就是我这几个板子都是用数组写的,所以会有memset或者for for for之类的,闲得很凌乱。再加上之前很智障地每次都要重新推一遍蝴蝶操作的Rev数组,就显得很弱智。于是决定下一次多项式复习的时候,自己可以学的更成体系,也可以用上operatorvector这两个利器。

upd:就在落笔不到5min之后想到了一个问题,就是你会发现在多项式题目里面有$\mod x^n$和$\mod \rm{NTTPrime}$ 两种约束,一直以为的是不同的运算有不同的约束,但这是$\color{red}{\text{错的}}$ 。真正的区别是,前者是对次数的约束,后者是对系数的约束。

= =也就只有我会智障到现在才明白。