bzoj2173:整数的lqp拆分

bzoj

luogu

生成函数做起来挺简单的

首先，答案显然是
\[ ans=[x^n]\sum_{i=1}^{+\infty}Fib^i(x)=[x^n]\frac{Fib(x)}{1-Fib(x)} \]

然后有
\[ Fib(x)=\frac{1}{1-x-x^2} \]
证明如下（知道自行往下走）
\[ Fib(x)=x+x^2+2x^3+3x^4+5x^5++8x^6+...\xFib(x)=x^2+x^3+2x^4+3x^5+5x^6++8x^7+...\Fib(x)-xFib(x)=x+x^3+x^4+2x^5+3x^6+...=x+x^2Fib(x)\Fib(x)-xFib(x)-x^2Fib(x)=x\Fib(x)=\frac{x}{1-x-x^2} \]

然后设
\[ G(x)=\frac{x}{1-2x-x^2}\G(x)-2G(x)x-G(x)x^2=x\G(x)=2G(x)x-G(x)x^2+x \]
于是可以得出递推式
\[ g(n)=2*g(n-1)+g(n-2) \]
代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
void read(int &x) {
    char ch; bool ok;
    for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
    for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}
#define rg register
const int maxn=1e5+10,mod=1e9+7;
int n,las1,las2,now;
int main()
{
    las2=0,now=las1=1;read(n);
    for(rg int i=2;i<=n;i++)now=(las1*2ll%mod+las2)%mod,las2=las1,las1=now;
    printf("%d\n",now);
}

bzoj2173:整数的lqp拆分

原文：https://www.cnblogs.com/lcxer/p/10863964.html