Luogu P4451 [国家集训队]整数的lqp拆分

题目描述

https://www.luogu.com.cn/problem/P4451

简要题意：令 $f_{n}$ 为斐波那契数第 $n$ 项，求 $\sum \prod_{i = 1}^{m} f_{a_{i}}$ ， $m > 0, a_{1}, a_{2}, \dots, a_{m} > 0, \sum_{i = 1}^{m} a_{i} = n$

$n \leq 10^{100000}$

Solution

令 $F (x)$ 为斐波那契数的生成函数，那么容易得到答案的生成函数就是 $\sum_{i = 0}^{\infty} F (x)^{i} - [n = 0] = \frac{1}{1 - F (x)} - [n = 0]$

我们考虑 $G (x) = \frac{1}{1 - F (x)}$ 这个生成函数，我们知道 $F (x) = \frac{x}{1 - x - x^{2}}$ ，那么 $G (x) = \frac{1 - x - x^{2}}{1 - 2 x - x^{2}}$ ，我们尝试求出它的递推式

我们知道分母的递推式就是 $a_{n} = 2 a_{n - 1} + a_{n - 2}$ ，我们将这个递推式乘上 $1 - x - x^{2}$ ，那么变成 $a_{n} - a_{n - 1} - a_{n - 2} = a_{n - 1} \to a_{n} = 2 a_{n - 1} + a_{n - 2}$ ，解特征方程能得到 $x_{1} = 1 - \sqrt{2}, x_{2} = 1 + \sqrt{2}$ ，我们知道 $a_{0} = 0, a_{1} = 1$ ，能够得到 $a_{n} = \frac{(1 + \sqrt{2})^{n} - (1 - \sqrt{2})^{n}}{2 \sqrt{2}}$

我们知道 $2$ 在 $1 e 9 + 7$ 下有二次剩余 $59713600$ ，那么我们直接做快速幂即可，注意指数要对 $φ (1 e 9 + 7)$ 取模

#include <iostream>
#include <cstring>
#define maxn 100010
#define ll long long
using namespace std;

const int p = 1000000007;
const int pp = 1000000006;
const int sqrt2 = 59713600;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s;
}

int n; 
char s[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> s + 1; n = strlen(s + 1); int k = 0;
    for (int i = 1; i <= n; ++i) k = (10ll * k + s[i] - '0') % pp;
    ll ans = (pow_mod(1 + sqrt2, k) - pow_mod(1 - sqrt2, k)) * pow_mod(2 * sqrt2, p - 2) % p;
    cout << (ans + p) % p << "\n";
    return 0;
}