fps - shakayami/ACL-for-python GitHub Wiki

fps

形式的べき級数ライブラリ

現在ではmod 998244353のみに対応しています。適切なところを書き換えれば、NTT-friendlyな素数ならば対応できると思います。

A=FPS([1,2,3,5,8])

とすると、A:=1+2x+3x^2+5x^3+8x^4という扱いになります。

A=FPS([1,2,3])
B=FPS([4,5,6,7])
print(A)
print(B)
print(A+B)
print(A-B)
print(A*B)
print(A/B)
print(A>>1)
print(A<<1)
A+=B
A-=B
A*=B
A/=B
A<<=1
A>>=1

それぞれ全部定義されています。

A=FPS([1,2,3])
print(A.diff())
#FPS([2,6])
print(A.integral())
#FPS([0,1,1,1])

微分と積分をします。有理数はmod 998244353で出力します。

注意：以下の提出リンク先のコードはライブラリが古いのでライブラリそのものはgithubの方からコピーすることを強く推奨します。

第一種スターリング数 FFTと分割統治を使う

第二種スターリング数

ベルヌーイ数母関数とinv of formal power seriesを使う

分割数母関数のlogはO(NlogN)で求められるため、exp of formal power seriesで復元する

分割数と似ている。少々ひねる必要がある。

実装するにあたって、以下のリンクを参考にしました。ありがとうございます！

ttps://opt-cp.com/fps-implementation/ はリンク切れしているので以下を参照