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

传送门:洛谷

解题思路:

考虑设$f(i)$为和为$i$的拆分权值和,那么我们可以得到一个递推关系式$$f(i)=\sum _{i=1}^{n}f(n-i)\ast fib(i)$$这个表达式的含义就是枚举一个数的值,由于分配率,我们给每一个和乘上一个数,相当于给整体乘上一个数
此时我们发现,$f(0)$应该为$1$,但是光光的由上面的式子,我们并不能得到$f(0)$为1,所以我们考虑补充定义$f(0)=1$
也就是说此时$$f(i)=[n=1]+\sum _{i=1}^{n}f(n-i)\ast fib(i)$$
发现很像一个卷积式子,但是下标不为$1$,因为$fib(0)=0$(这意味着常数项一定为0,不会影响$f(0)$的值),所以我们不妨考虑临时扩展上述式子,可以得到:
$$f(i)=[n=1]+\sum _{i=0}^{n}f(n-i)\ast fib(i)$$
所以我们可以得到,$F=F\ast FIB+1$
化解一下可以得到$F=\frac{1}{1-FIB}$,对于$FIB$数列,我们有一个生成函数的结论(限于篇幅,此处不证)
$$FIB=\frac{x}{1-x-x^2}$$
所以此时我们可以很轻易的写出$F$的生成函数,$$F=1+\frac{x}{1-2\ast x-x^2}$$
我们现在需要做的事就是将$F$展开回去,因为$F[1]=1$,所以1可以直接分开拿出来,现在考虑后面的那一个分式.
根据套路,这应该是一个可以裂项的式子,考虑待定系数法来裂项,
我们可以得到$$\frac{x}{1-2\ast x-x^2}=\frac{\sqrt{2}}{4}\ast (\frac{1}{1-(1+\sqrt{2})x}-\frac{1}{1-(1-\sqrt{2})x})$$
根据一些生成函数的小结论,${\sum }_{i=0}^{\infty }{x}^i=\frac{1}{1-x}$

我们对上述式子进行展开,可以得到:
$$F=1\ast x^0+\frac{\sqrt{2}}{4}\ast \sum _{i=0}^{\infty }((1+\sqrt{2}{)}^i-(1-\sqrt{2}{)}^i)x^i$$

不难看出,我们最终的答案就是$(1+\sqrt{2}{)}^i-(1-\sqrt{2}{)}^i$
此时还需要考虑$\sqrt{2}$的二次剩余,也就是考虑这样的一个同余方程:
$$x^2\equiv 2modp$$
因为我们现在并不是解决二次剩余问题,我们只需要求出一个数的二次剩余,所以我们大可以在本地跑出这个式子的答案.

至此,本题解决.

---

下面是本题的代码部分:

#include 
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
inline void print(__int128 x){
	if(x<0) {putchar('-');x=-x;}
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
#define maxn 1000000
#define int long long
const int mod=1e9+7;
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int qpow(int a,int b) {
	int ans=1;
	while(b) {
		if(b&1) ans=ans*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}
int sqrt2=59713600;
void init() {
	for(int i=1;i<=mod;i++) {
		if(i*i%mod==2) {
			sqrt2=i;break;
		}
	}
}
signed main() {
	int n=0;string s;cin>>s;
	for(int i=0;i<s.length();i++) n=(n*10+s[i]-'0')%(mod-1);
//	init();
	cout<<(qpow(1+sqrt2,n)-qpow((1-sqrt2+mod)%mod,n)%mod+mod)%mod*qpow(2*sqrt2%mod,mod-2)%mod<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49