P4451 [国家集训队]整数的lqp拆分 做题记录

给定 nn,求

m>0,ai>0,ai=ni=1mFai\sum\limits_{m>0,a_i>0,\sum a_i=n}\prod_{i=1}^m F_{a_i}

109+710^9 + 7 取模。

1n101001\le n\le 10^{100}

F(x)=x2F(x)+xF(x)+xx=(1xx2)F(x)F(x)=x1xx2\begin{aligned} F(x)&=x^2F(x)+xF(x)+x\\ x&=(1-x-x^2)F(x)\\ F(x)&=\frac{x}{1-x-x^2} \end{aligned}

G(x)=G(x)F(x)+F(x)G(x)(1F(x))=F(x)G(x)=F(x)1F(x)G(x)=x1xx21x1xx2G(x)=x1xx212xx21xx2G(x)=x12xx2\begin{aligned} G(x)&=G(x)F(x)+F(x)\\ G(x)(1-F(x))&=F(x)\\ G(x)&=\frac{F(x)}{1-F(x)}\\ G(x)&=\frac{\frac{x}{1-x-x^2}}{1-\frac{x}{1-x-x^2}}\\ G(x)&=\frac{\frac{x}{1-x-x^2}}{\frac{1-2x-x^2}{1-x-x^2}}\\ G(x)&=\frac{x}{1-2x-x^2}\\ \end{aligned}

设 x12xx2=b1ax+d1cx=bcbx+ddax1cxax+acx2=(b+d)+(cbda)x1+(c+a)x+acx2\begin{aligned} \text{设 }\frac{x}{1-2x-x^2}&=\frac{b}{1-ax}+\frac{d}{1-cx}\\ &=\frac{b-cbx+d-dax}{1-cx-ax+acx^2}\\ &=\frac{(b+d)+(-cb-da)x}{1+(c+a)x+acx^2}\\ \end{aligned}

{b+d=0cbda=1c+a=2ac=1\begin{cases} b+d=0\\ -cb-da=1\\ c+a=-2\\ ac=-1 \end{cases}

解得:(其实有两组解,但本质相同)

{c=1+2a=12d=24b=24\begin{cases} c=1+\sqrt2\\ a=1-\sqrt2\\ d=\frac{\sqrt2}{4}\\ b=\frac{-\sqrt2}{4} \end{cases}

所以:

x12xx2=b1ax+d1cx=24i=0(12)ixi+24i=0(1+2)ixi\begin{aligned} \frac{x}{1-2x-x^2}&=\frac{b}{1-ax}+\frac{d}{1-cx}\\ &=-\frac{\sqrt2}{4}\sum\limits_{i=0}^\infin(1-\sqrt2)^ix^i+\frac{\sqrt2}{4}\sum\limits_{i=0}^\infin(1+\sqrt2)^ix^i\\ \end{aligned}

所以:

gn=24((1+2)n(12)n)g_n=\frac{\sqrt2}{4}((1+\sqrt2)^n-(1-\sqrt2)^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;
}