Picks's Blog

Polynomial Division

| Comments

引入

于是开始正题:多项式除法啦。
前置技能:多项式求逆
有了多项式求逆之后将除法就很简单了……

问题概述

给出多项式 ,求出多项式 ,满足:

其中: 表示 的最高次项的次数。

多项式除法

不妨令:

假如我们可以把多项式放到模 意义下,那很多操作都会很好做了。
这样,我们就要排除掉 的影响。
怎么做呢?定义:

考虑下这个变换的形式理解,即将多项式的系数翻转,高次项的到低次项来,低次项的到高次项去。
那么不妨将最初的等式两边的 替换为 ,再都乘以 ,看能得到什么。

放至模意义下!就消去了 带来的影响!

注意到 ,故 不会受到模意义的影响!
我们可以利用多项式求逆算出 ,用FFT算出 ,然后代入最开始的式子中,就可以解得 了。
注意到由于 项必然不为0,故 的第0项必然不为0。则逆元一定存在。
复杂度:

代码

代码还是有点长的……

void Division( int A[], int B[], int D[], int R[], int N, int M ) {
    FOR ( i, 0, N - M ) { D[ i ] = A[ N - i ]; } FOR ( i, N - M + 1, K - 1 ) { D[ i ] = 0; }
    int K; for ( K = 1; K < 2 * N; K <<= 1 ); int invK = fpm( K, P - 2, P );
    GetInv( invB, B, N - M + 1 );
    FFT( invB, K, 0 ); FFT( D, K, 0 );
    FOR ( i, 0, K - 1 ) { D[ i ] = (ll)D[ i ] * invB[ i ] % P; }
    FFT( D, K, 1 );
    FOR ( i, 0, N - M ) { D[ i ] = (ll)D[ i ] * invK % P; } FOR ( i, N - M + 1, K - 1 ) { D[ i ] = 0; }
    FOR ( i, 0, ( N - M ) / 2 ) { swap( D[ i ], D[ N - M - i ] ); }
    FOR ( i, 0, N - M ) { tmp[ i ] = D[ i ]; } FOR ( i, N - M + 1, K - 1 ) { tmp[ i ] = 0; }
    FFT( tmp, K, 0 );
    FOR ( i, 0, K - 1 ) { tmp[ i ] = (ll)tmp[ i ] * B[ i ] % P; }
    FFT( tmp, K, 1 );
    FOR ( i, 0, M - 1 ) { tmp[ i ] = (ll)tmp[ i ] * invK % P; } FOR ( i, M, K - 1 ) { tmp[ i ] = 0; }
    FOR ( i, 0, M - 1 ) { R[ i ] = A[ i ] - tmp[ i ]; } FOR ( i, M, K - 1 ) { R[ i ] = 0; }
}

应用

多点求值

问题概述

给出多项式 ,求出其在 处的取值。

解决方法

构造多项式:

那么,令:

我们能得到一个性质:

因为模去的多项式中已经包含了 ,值必然为0.
递归到两边求值就好。
复杂度:.

常系数齐次线性递推

问题概述

给出递推关系 ,以及初值 ,求 .

解决方法

首先需要研究一下叉姐的论文:《线性递推关系与矩阵乘法》。这里只讲其中可以用多项式除法优化的部分。
设转移矩阵为 ,其特征多项式为 .
由 Cayley-Hamilton 定理,.
而我们需要对转移矩阵进行快速幂。我们考虑将 表示成 的线性表示。
每次平方,直接视作多项式乘法。
如何将溢出 的部分压回来?利用
我们只需要将溢出去的部分对 取模即可!
这样就能做到 了。

多项式欧几里德算法

问题概述

给出多项式 ,求他们的公因式。

解决方法

类比与欧几里德算法,我们可以证明欧几里德算法需要的结论在多项式上均成立。
考虑使用欧几里德算法。
每次相当于求两个多项式的商与余数。
正好可以利用多项式除法解决。
不过每次取模均只能将最高次减小1。
复杂度:.

多项式求逆EXT

问题概述

给出多项式 ,求 在模 意义下的逆元

解决方法

转为求:

使用多项式扩展欧几里德算法就好。和多项式欧几里德算法区别不大?
同样的,可以求出:

代码写得太丑还是不放了……反正主要的就是多项式除法部分了啦啦啦……

Comments

comments powered by Disqus