洛谷 4451 整数的 lqp 拆分

发表于 | 分类于 |

所以实际上是个水题……
哪来的黑啊……

考虑斐波那契数列的生成函数即 \[ F(x) = \sum\limits_{n=0}^{\infty} F_n x^n = \frac x{1-x-x^2} \]

注意到这个拆分是考虑顺序的，故设答案的生成函数为 \(G\)，则枚举划分为几部分有 \[ G(x) = \sum\limits_{n=1}^{\infty} F^n(x) = \frac1{1-F(x)} - 1 \]

（然后多项式求逆就行了！太简单了哇）
在 BZOJ 上和以前的洛谷这道题上是可行的，当时数据仅 \(10^6\)，常数比较小的话是可以过的。
然而……
不如找个通项出来。

显然 \[ G(x) = \frac1{1-F(x)}- 1 = \frac1{1-\frac x{1-x-x^2}} - 1 = \frac x{1-2x-x^2} \] 将分母因式分解成 \((1-ax)\) 相乘的形式，有 \[ G(x) = \frac x{1-2x-x^2} = \frac x{[1-(1-\sqrt 2)x][1-(1+\sqrt 2)x]} \] 部分分式展开有 \[ G(x) = \frac x{[1-(1-\sqrt 2)x][1-(1+\sqrt 2)x]} = \frac 1{2\sqrt 2}\left(\frac1{1-(1+\sqrt 2)x} - \frac1{1-(1-\sqrt 2)x}\right) \]

易得第 \(n\) 项为 \(\frac1{2\sqrt 2}((1+\sqrt2)^n-(1-\sqrt2)^n)\)。
注意到 \(2\) 在模 \(10^9+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
#include <cstdio>
using namespace std;
const int mod = 1e9 + 7;
int n;
inline int read()
{
    int ret = 0;
    char ch = 0;
    for(;ch < '0' || ch > '9';ch = getchar());
    for(;ch >= '0' && ch <= '9';ret = (10LL * ret + ch - '0') % (mod - 1),ch = getchar());
    return ret;
}
inline int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
int main()
{
    n = read();
    printf("%lld\n",14928400LL * (fpow(59713601,n) - fpow(940286408,n) + mod) % mod);
}