P4451 [国家集训队]整数的lqp拆分 生成函数

题意：

戳这里

分析：

先推一波斐波那契的生成函数

[F(x)=x+x^2+2x^3dots f_n x^n \ xF(x)=x^2+x^3dots f_nx^{n+1} \ x^2F(x)=x^3dots f_nx^{n+2} \ herefore F(x)=x+xF(x)+x^2F(x) \ F(x)=frac{x}{1-x-x^2} ]

我们统计的答案就是

[G(x)=sum_{i=0}^{infty} F(i)x^i=frac{1}{1-F(x)}=frac{1}{1-frac{x}{1-x-x^2}}=frac{1-x-x^2}{1-2x-x^2}=1+frac{x}{1-2x-x^2} ]

我们现在要通过 OGF 反推原序列，根据 著名的恒等式 (displaystyle frac{1}{1-ax}=sum_{i=0}^{infty} a^ix^i) 我们要尽力的把上面式子的第二项向这个形式上化简

[frac{x}{1-2x-x^2} \ =-frac{x}{(x-x1)(x-x2)} \ =frac{x}{x1-x2}(frac{1}{x-x1}-frac{1}{x-x2}) \ =frac{x}{x1-x2}(frac{1}{x1}*frac{1}{1-frac{x}{x1}}-frac{1}{x2}*frac{1}{1-frac{x}{x2}}) \ =frac{x}{x1-x2}(frac{1}{x1}*sum_{i=0}^{infty}(frac{x}{x1})^i-frac{1}{x2}*sum_{i=0}^{infty}(frac{x}{x2})^i) \ =frac{1}{x1-x2}(sum_{i=0}^{infty}(frac{x}{x1})^{i+1}-sum_{i=0}^{infty}(frac{x}{x2})^{i+1}) ]

那么第 (n) 项 （次数为 (n-1) ）的系数为 (frac{1}{x1-x2}(sum_{i=0}^{infty}(frac{1}{x1})^n-sum_{i=0}^{infty}(frac{1}{x2})^n))

将 (x1,x2) 等于 (-1pmsqrt 2) 带入

([x^n]=frac{sqrt 2}{4}((1+sqrt2)^n-(1-sqrt 2)^n))

代码：

#include<bits/stdc++.h>
#define inl inline
#define reg register

using namespace std;

namespace zzc
{
	typedef long long ll;
	const ll mod = 1e9+7;
	const ll sqr = 59713600;
	
	inline ll read()
	{
		ll x=0,f=1;char ch=getchar();
		while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
		while(isdigit(ch)){x=(x*10+ch-48)%(mod-1);ch=getchar();}
		return x*f;
	}
	
	ll qpow(ll x,ll y)
	{
		ll res=1;
		while(y)
		{
			if(y&1) res=res*x%mod;
			x=x*x%mod;
			y>>=1;
		}
		return res;
	}

	void work()
	{
		ll n=read();
		printf("%lld
",(sqr/4*(qpow(sqr+1,n)-qpow(mod-sqr+1,n)+mod)%mod)%mod);
	}

}

int main()
{
	zzc::work();
	return 0;
}