No.980 Fibonacci Convolution Hard - yukicoder

問題

数列 $(a_i)$ を以下の漸化式で定める．

• $a_1 = 0, a_2 = 1$
• $a_n = p a_{n - 1} + a_{n - 2} \quad (n \geq 3)$

$q$ 個のクエリが与えられる． $i$ 番目のクエリでは，整数 $m_i$ に対し $\sum_{s + t = m_i} a_s a_t$ を求めよ．

制約

• $1 \leq p \leq 10^9$
• $1 \leq q \leq 2 \cdot 10^5$
• $2 \leq m_i \leq 2 \cdot 10^6$

考察

$b_i = \sum_{s + t = i} a_s a_t$ とすると， $(a_i), (b_i)$ の母関数はそれぞれ $F(x) = \sum_{i = 0}^{\infty} a_i x^i$ ， $G(x) = \sum_{i = 0}^{\infty} b_i x^i$ となる( $a_0 = 0$ とする)． すると $(b_i)$ は $(a_i)$ の和に関する畳み込みなので， $G(x) = (F(x))^2$ が成り立つ．

さらに $a_n - pa_{n - 1} - a_{n - 2} = 0$ から，項をずらして打ち消させる要領で，

$$ F(x) = \frac{x^2}{1 - px - x^2} $$

が成り立つ¹．ここから，

$$ G(x) = (F(x))^2 = \frac{x^4}{(1 - px - x^2)^2} = \frac{x^4}{1 - 2px + (p^2 - 2) x^2 + 2px^3 + x^4} $$

となる．最後にさっきの $F(x)$ に施した変形の逆操作を考えると，

• $b_1 = b_2 = b_3 = 0, b_4 = 1$
• $b_n = 2pb_{n - 1} - (p^2 - 2)b_{n - 2} - 2pb_{n - 3} - b_{n - 4}$

という漸化式が立つ．後はこれを必要な分だけ前計算しておけばよい．

実装例

#424001 (C++17(clang)) No.980 Fibonacci Convolution Hard - yukicoder

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <iostream>
#include <vector>

using lint = long long;

template <int MOD>
struct ModInt { ... };

constexpr int MOD = 1e9 + 7;
using mint = ModInt<MOD>;

constexpr int N = 2000000;

void solve() {
    mint p;
    std::cin >> p;

    std::vector<mint> xs(N + 1, 0);
    xs[4] = 1;
    for (int i = 5; i <= N; ++i) {
        xs[i] = xs[i - 1] * p * 2 - xs[i - 2] * (p * p - 2) -
                xs[i - 3] * p * 2 - xs[i - 4];
    }

    int q;
    std::cin >> q;
    while (q--) {
        int n;
        std::cin >> n;
        std::cout << xs[n] << std::endl;
    }
}