bzoj 4002 有意义的字符串

Posted on | Views:

数学套路题.

考虑将 $\frac {b+\sqrt d}{2}$ 写成某个递推数列的特征方程的根.

设数列 $a_i=A\cdot (\frac{b+\sqrt d}{2})^i+B\cdot (\frac{b-\sqrt d}{2})^i$ .

可以根据韦达定理得出该数列的递推式 $a_i=b\cdot a_{i-1}+\frac{d-b^2}{4}\cdot a_{i-2}$ .

令 $A=B=1$ ,得到这个数列的前两项 $a_1=b,a_2=\frac{b^2+d}{2}$ .

由于 $b\bmod 2=1,d\bmod 4=1$ ,所以 $\frac {d-b^2}{4},\frac{b^2+d}{2}$ 一定是个整数.

于是可以用矩阵快速幂求出 $a_n$ .

而 $(\frac{b+\sqrt d}{2})^n=a_n-(\frac{b-\sqrt d}{2})^n$ ,答案需要向下取整.

有限制 $0<b^2\leq d<(b+1)^2$ ,所以有 $(\frac {b-\sqrt d}{2})^n\in(-1,0]$ .

于是当且仅当 $b^2<d,n\bmod 2=0​$ 时,答案为 $a_n-1​$ ,其余情况为 $a_n​$ .

时间复杂度 $O(\log n)​$ .

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const ll P=7528443412579576937;
ll add(ll a,ll b)
{
	return (P-a<=b)?(a-P+b):(a+b);
}
ll mul(ll a,ll b)
{
	ll res=a*b-(ll)((long double)a/P*b+1e-8)*P;
	return res<0?res+P:res%P;
}
struct Matrix
{
	ll v[2][2];
	Matrix(){memset(v,0,sizeof v);}
	Matrix operator * (const Matrix &rhs) const
	{
		Matrix res;
		for(int i=0;i<2;++i)
			for(int k=0;k<2;++k) if(v[i][k])
				for(int j=0;j<2;++j)
					res.v[i][j]=add(res.v[i][j],mul(v[i][k],rhs.v[k][j]));
		return res;
	}
}st,trans,I;
Matrix fpow(Matrix a,ll b)
{
	Matrix res=I;
	while(b)
	{
		if(b&1)
			res=res*a;
		a=a*a;
		b>>=1;
	}
	return res;
}
int main()
{
	I.v[0][0]=I.v[1][1]=1;
	ll b=read(),d=read(),n=read();
	if(n==0)
		return printf("1\n")&0;
	if(n==1)
		return printf("%lld\n",floor((double)((b+sqrt(d))/2)))&0;
	st.v[0][0]=((b*b+d)/2)%P,st.v[1][0]=b;
	trans.v[0][0]=b,trans.v[0][1]=((d-b*b)/4)%P,trans.v[1][0]=1;
	st=fpow(trans,n-2)*st;
	ll ans=st.v[0][0];
	if(n%2==0 && b*b<d)
		--ans;
	cout<<ans<<endl;
	return 0;
}