给定 n,求
m>0,ai>0,∑ai=n∑∏i=1mFai
对 109+7 取模。
1≤n≤10100。
F(x)xF(x)=x2F(x)+xF(x)+x=(1−x−x2)F(x)=1−x−x2x
G(x)G(x)(1−F(x))G(x)G(x)G(x)G(x)=G(x)F(x)+F(x)=F(x)=1−F(x)F(x)=1−1−x−x2x1−x−x2x=1−x−x21−2x−x21−x−x2x=1−2x−x2x
设 1−2x−x2x=1−axb+1−cxd=1−cx−ax+acx2b−cbx+d−dax=1+(c+a)x+acx2(b+d)+(−cb−da)x
⎩⎪⎪⎪⎨⎪⎪⎪⎧b+d=0−cb−da=1c+a=−2ac=−1
解得:(其实有两组解,但本质相同)
⎩⎪⎪⎪⎨⎪⎪⎪⎧c=1+2a=1−2d=42b=4−2
所以:
1−2x−x2x=1−axb+1−cxd=−42i=0∑∞(1−2)ixi+42i=0∑∞(1+2)ixi
所以:
gn=42((1+2)n−(1−2)n)
代码如下:
// Problem: P4451 [国家集训队]整数的lqp拆分
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4451
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <iostream>
#include <cstdio>
using namespace std;
const int p=1000000007,sq2=59713600;
inline int qpow(int x,int y)
{
int res=1;
for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
return res;
}
int n;
inline int read()
{
int s=0,c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') s=(1ll*s*10+c-48)%(p-1),c=getchar();
return s;
}
int main()
{
n=read();
printf("%d\n",1ll*sq2*qpow(4,p-2)%p*(qpow(1+sq2,n)-qpow(1-sq2+p,n)+p)%p);
return 0;
}