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

给定 $n$，求

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

对 $10^9 + 7$ 取模。

$1\le n\le 10^{100}$。

$\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}$

$\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}$

$\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}$

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

解得：（其实有两组解，但本质相同）

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

所以：

$\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}$

所以：

$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;
}