2019.03.29【洛谷P4451】【BZOJ2173】整数的lqp拆分（生成函数）

洛谷传送门

BZOJ传送门

---

解析：

设$g_i$gi​表示一个整数的lqp拆分的权值，其生成函数为$G(x)$G(x)，$f_i$fi​表示第$i$i个斐波那契数，生成函数为$F(x)$F(x)。

令$g_0=0,g_1=1$g0​=0,g1​=1

很显然我们可以发现：
$g_n=\sum_{i=1}^{n}g_if_{n-i}+f_n\\ G=G*F+F$gn​=i=1∑n​gi​fn−i​+fn​G=G∗F+F

也就是$G=\frac{F}{1-F}$G=1−FF​

我们知道斐波那契数列的生成函数闭形式是$F=\frac{1}{1-x-x^2}$F=1−x−x21​，代到上面去可以得到$G=\frac{x}{1-2x-x^2}$G=1−2x−x2x​。

也就是$G=2xG+x^2G+x$G=2xG+x2G+x，最后面那个$1$1是对于$g_1$g1​的，不用管，对于$i>1$i>1，我们得到递推式$g_i=2g_{i-1}+g_{i-2}$gi​=2gi−1​+gi−2​。

推到这里已经可以过这道题了，那么我们把$n$n放到$1e18$1e18如何？

显然我们继续推是可以得到通项公式的。

拆掉分母：$\frac{x}{1-2x-x^2}=\frac{x}{(1- (1-\sqrt 2 )x)(1-(1+\sqrt 2 )x)}$1−2x−x2x​=(1−(1−2​)x)(1−(1+2​)x)x​

待定系数，设$G=\frac{a}{(1-\sqrt 2 )x}+\frac{b}{1-(1+\sqrt 2 )x}$G=(1−2​)xa​+1−(1+2​)xb​

恒等变形解得$a=-\frac{\sqrt 2}{4},b=\frac{\sqrt 2}{4}$a=−42​​,b=42​​

随手写一个二次剩余，或者直接暴力$1e9+7$1e9+7，也不慢，$10s$10s内随便跑出来，我们得到$59713600^2\equiv 2\pmod{1e9+7}$597136002≡2(mod1e9+7)

通项公式：$g_n=\frac{\sqrt 2}{4}((1+\sqrt 2)^n-(1-\sqrt 2)^n)$gn​=42​​((1+2​)n−(1−2​)n)

---

代码：（递推）

#include<bits/stdc++.h>
#define ll long long
#define re register
#define cs const

cs int mod=1e9+7;
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
int n;
int g[1000006];
signed main(){
	std::cin>>n;
	g[1]=1;
	for(int re i=2;i<=n;++i)g[i]=add(add(g[i-1],g[i-1]),g[i-2]);
	std::cout<<g[n]<<"\n";
	return 0;
}

代码：（通项）

#include<bits/stdc++.h>
#define ll long long
#define re register
#define cs const

cs int mod=1e9+7;
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(int a,int b){return a<b?a-b+mod:a-b;}
inline int mul(int a,int b){return (ll)a*b%mod;}
inline int quickpow(int a,int b,int res=1){
	while(b){
		if(b&1)res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}

cs int sqr2=59713600,inv2=(mod+1)>>1;

int n;
signed main(){
	std::cin>>n;
	std::cout<<mul(mul(sqr2,mul(inv2,inv2)),dec(quickpow(add(1,sqr2),n),quickpow(dec(1,sqr2),n)));
	return 0;
}