はまやんはまやんはまやん

hamayanhamayan's blog

Fibonacci Convolution Hard [yukicoder 980]

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

前提知識

解説

https://yukicoder.me/submissions/424776

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

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

求めたいものは畳み込み計算されたものになる。
2数列の畳み込みは、母関数の積で計算可能なので、畳込み計算した求めたい数列をBとすると、
母関数はg(T)={f(T)}^2となる。
きれいにすると、g(T)=T4/(1-2pT+(p2-2)T2+2pT3+T4)となる。
分子が初期値になってるので、B[0]=B[1]=B[2]=B[3]=0, B[4]=1が初期値。
分母が遷移になっているので、B[n]=2pB[n-1]+(2-p2)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());
    }
}