洛谷 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);
}