FPS(Formal Power Series,形式的冪級数)
このページはFPSについて説明するページではなく、有用そうな情報を個人的に置いておくページです
FPSについて知りたい人は下の五つの記事が参考になると思います。
参考：
optさんの記事 ライブラリと使い方が載っているので、概念を理解した後実装するときに役に立つ。 maspyさんの記事 概念を理解していないならまずはこれを頑張って読む。なんとなく気持ちがわかってきたら、 hamamuさんの記事 この記事に載っている問題を実際に解いてみる。FPS関連のデータベースとして充実している みちらからさんの記事 基本的な概念の理解に役立ちそう。maspyさんの記事よりも初心者向けで読みやすい ざっくり
dpを多項式で表してみると高速に計算できてうれしいね！みたいな話（？）
FFT等はまだ理解していないが、内部実装を知らなくてもある程度までは使えるようにしておくと便利だと思っている
optさんのFPSを使わせて頂いている。何もわからない僕にとっては一番使いやすい。
スニペットに登録して呼び出せるようにしておくとよい
FPS a(n)で、長さn(に制限した)多項式を宣言する。
aがすべて0だと何も起きないのでa[0]=1とする
0の部分が多い場合はsfpsを使う。sfpsは{場所,数}のペアのvectorで、これをFPSにかけたり割ったりできる
divide、multiplyはsfpsの単体バージョンで、定数倍が良いらしい。
FPS同士の掛け算もできる
重要な話
FPSライブラリで殴るのがFPSではない。FPSで考察を進めていくうちに、最終的に二項係数の式に帰着出来て解ける場合が多い。式変形で機械的に問題を整理できるのがFPSの強み。
例えば$ \frac{1}{x-1} = 1 + x+x^2+x^3+x^4\dotsという式はよく出てくるイメージ。この式変形は #自己ループを含む期待値DP でも出てくる。 とりあえずFPSで殴れた問題の提出コードのリンクを置いておく
code:cpp
void _main(){
LL(n,m);
COMinit();
FPS a(m+2);
rep(i,14){
sfps b;
rep(j,0,n+1,2){
if((1<<i)*j>m)break;
b.pb({(1<<i)*j,COM(n,j)});
}
a *= b;
}
}