洛谷 4451 整数的 lqp 拆分

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

考虑斐波那契数列的生成函数即 F(x)=∞∑n=0Fnxn=x1−x−x2

注意到这个拆分是考虑顺序的，故设答案的生成函数为 G，则枚举划分为几部分有 G(x)=∞∑n=1Fn(x)=11−F(x)−1

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

显然 G(x)=11−F(x)−1=11−x1−x−x2−1=x1−2x−x2

将分母因式分解成 (1−ax) 相乘的形式，有 G(x)=x1−2x−x2=x[1−(1−√2)x][1−(1+√2)x]

部分分式展开有 G(x)=x[1−(1−√2)x][1−(1+√2)x]=12√2(11−(1+√2)x−11−(1−√2)x)

易得第 n 项为 12√2((1+√2)n−(1−√2)n)。
注意到 2 在模 109+7 意义下是有二次剩余的，于是直接快速幂即可。

代码：

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