DDOSvoid's Blog

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

发表于 分类于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

题目描述

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

简要题意：令 $f_n$ 为斐波那契数第 $n$ 项，求 $\sum \prod_{i=1}^m f_{a_i}$，$m>0,a_1,a_2,\cdots,a_m>0,\sum_{i=1}^ma_i=n$

$n\le 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-2x-x^2}$，我们尝试求出它的递推式

我们知道分母的递推式就是 $a_n=2a_{n-1}+a_{n-2}$，我们将这个递推式乘上 $1-x-x^2$，那么变成 $a_n-a_{n-1}-a_{n-2}=a_{n-1}\rightarrow a_n=2a_{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$ 在 $1e9+7$ 下有二次剩余 $59713600$，那么我们直接做快速幂即可，注意指数要对 $\varphi(1e9+7)$ 取模

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
#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;
}