Picks's Blog

Inverse Element of Polynomial

| Comments

引入

写一点跟多项式除法有关的内容吧。感觉挺有意思的。
首先便是前置技能多项式求逆元。
其实感觉多项式求逆元的用处在OI中比多项式除法还多呢233

问题概述

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

多项式求逆元

这里我们将使用一种倍增的思想来完成。
首先,当 时, .
假如我们已经求出了在模 意义下的答案 ,要求在 意义下的答案。
那么:

由于 逆元 存在,故得:

那么我们将等式各部分平方,展开后得:

两边同乘 ,利用逆元的性质移项便可得:

上式便可在 时间内求出了。
由于每次是倍增的,所以总复杂度:

可得为 .

代码

注意一下实现技巧……在单次运算时可以只用3次FFT……

void GetInv( int A[], int A0[], int t ) {
    if ( t == 1 ) { A0[ 0 ] = fpm( A[ 0 ], P - 2, P ); return; }
    GetInv( A, A0, ( t + 1 ) >> 1 );
    int k = 1; for ( ; k <= ( t << 1 ) + 3; k <<= 1 ); int inv_k = fpm( k, P - 2, P );
    FOR ( i, 0, t - 1 ) { tmp[ i ] = A[ i ]; } FOR ( i, t, k - 1 ) { tmp[ i ] = 0; }
    FFT( tmp, k, 0 ); FFT( A0, k, 0 );
    FOR ( i, 0, k - 1 ) { tmp[ i ] = 2 - (ll)tmp[ i ] * A0[ i ] % P + P; mod( tmp[ i ] ); }
    FOR ( i, 0, k - 1 ) { A0[ i ] = (ll)A0[ i ] * tmp[ i ] % P; }
    FFT( A0, k, 1 );
    FOR ( i, 0, t - 1 ) { A0[ i ] = (ll)A0[ i ] * inv_k % P; } FOR ( i, t, k - 1 ) { A0[ i ] = 0; }
}

应用

求Bernoulli数

问题简述

求出Bernoulli数前100000项模1998585857.

解决方法

利用Bernoulli数的指数型母函数即可。对 进行泰勒展开。

观察到最后的形式!不就是多项式的逆元吗!
那么我们把这个母函数放在模 意义下求出来,每一项也就得到了。
进一步推广,对于任意数列,只要其母函数的形态与上面形式类似,我们就能在 时间内得到其前 项!

替代分治+FFT

问题简述

个点组成的无向连通图个数,答案模1998585857.

分治+FFT做法

首先我们可以观察出答案的递推式:

注意到后面那一坨是个卷积,那么就可以直接分治+FFT了!
复杂度 .

多项式除法

我们不妨进行一些变换:

会发现本来的左边的式子形式和右边的差不多!那么直接卷积呢?
那么实际上我们就是两个向量卷积等于另一个向量了!

那么只要求出 在模 意义下的逆元,乘上 ,就可以得到答案了!
复杂度 .

Comments

comments powered by Disqus