Fibonacci Convolution Hard [yukicoder 980]

https://yukicoder.me/problems/no/980

前提知識

• 母関数

解説

https://yukicoder.me/submissions/424776

問題を見ると数列を作成して、畳込み計算をすれば答えられる。
今回は、各所で解説されている母関数で解く方法を解説しよう。

まず、元々の数列は線形漸化式になっているので、多項式の積によって遷移を表現することができる。
母関数をf(T)=A[1] T + A[2] T² + ...としておこう。
すると、1回の遷移は(pT+T²)の積で表現できるので、
f(T)=f(T)(pT+T²) + T²
と表現できる。最後のT²は初期値A[2]=1を反映している。
きれいにするとf(T)=T²/(1-pT-T²)となる。

求めたいものは畳み込み計算されたものになる。
2数列の畳み込みは、母関数の積で計算可能なので、畳込み計算した求めたい数列をBとすると、
母関数はg(T)={f(T)}^2となる。
きれいにすると、g(T)=T⁴/(1-2pT+(p²-2)T²+2pT³+T⁴)となる。
分子が初期値になってるので、B[0]=B[1]=B[2]=B[3]=0, B[4]=1が初期値。
分母が遷移になっているので、B[n]=2pB[n-1]+(2-p²)B[n-2]-2pB[n-3]-B[n-4]となる。
これを事前計算しておけば、クエリでは答えるだけになる。

int p, Q;
mint B[2010101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> p >> Q;
    
    B[4] = 1;
    rep(i, 5, 2010101) {
        B[i] = B[i - 1] * 2 * p
            + (mint(2) - mint(p) * mint(p)) * B[i - 2]
            - B[i - 3] * 2 * p
            - B[i - 4];
    }

    rep(_, 0, Q) {
        int q; cin >> q;
        printf("%d\n", B[q].get());
    }
}