[JLOI2015]有意义的字符串

4002: [JLOI2015]有意义的字符串

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1000 Solved: 436
[Submit][Status][Discuss]

Description

B 君有两个好朋友，他们叫宁宁和冉冉。有一天，冉冉遇到了一个有趣的题目：输入 b;d;n，求

Input

一行三个整数 b;d;n

Output

一行一个数表示模 7528443412579576937 之后的结果。

Sample Input

1 5 9

Sample Output

HINT

其中 0<b^2< = d<(b+1)2< = 10^18,n< = 10^18，并且 b mod 2=1,d mod 4=1

一开始幼稚的以为可以把sqrt(d)在%7528443412579576937 同余系下表示成一个整数，但后来发现我太naive了。

可以先找到((b+sqrt(d))/2)^n的共轭函数((b-sqrt(d))/2)^n，设这两者的和为f[n]。

那么我们相当于知道了两个基底等比数列，来构造出f[i]的递推式。

显然两个基底的只能是和前两项有关，于是我们设f[i+2]+ k * f[i+1] + p * f[i] =0

那么，可以得到 x^2 + k*x + p =0。

这个方程的两个根分别是 (b+sqrt(d))/2 和 (b-sqrt(d))/2

所以我们带回去就可以求得k和p。

然后就可以开开心心的用矩阵快速幂求 f[n]了。

但问题是怎么减去共轭函数的另一支呢？

有一个结论是当且仅当 b==d^2且n为偶数的时候需要-1，但是我也不知道为什么2333。

#include<bits/stdc++.h>

#define ll unsigned long long

using namespace std;

const ll ha=7528443412579576937ll;

inline ll add(ll x,ll y){

	x+=y;

	return x>=ha?x-ha:x;

}

inline ll ksc(ll x,ll y){

	ll an=0;

	for(;y;y>>=1,x=add(x,x)) if(y&1) an=add(an,x);

	return an;

}

inline ll ksm(ll x,ll y){

	ll an=1;

	for(;y;y>>=1,x=ksc(x,x)) if(y&1) an=ksc(an,x);

	return an;

}

const ll inv=ksm(2,ha-2);

const ll INV=ksc(inv,inv);

ll B,D,N;

struct node{

	ll a[2][2];

	node operator *(const node &u)const{

		node r;

		for(int i=0;i<=1;i++)

		    for(int j=0;j<=1;j++){

		    	r.a[i][j]=add(ksc(a[i][0],u.a[0][j]),ksc(a[i][1],u.a[1][j]));

			}

		return r;

	}

}ans,x;

inline void solve(){

	ans.a[0][0]=ans.a[1][1]=1;

	ans.a[0][1]=ans.a[1][0]=0;

	ll O=N;

	N--;

	for(;N;N>>=1,x=x*x) if(N&1) ans=ans*x;

	ll an=0;

	an=add(ksc(2,ans.a[0][1]),ksc(B,ans.a[1][1]));

	if(ksc(B,B)!=D&&!(O&1)) an=add(an,ha-1);

	printf("%lld\n",an);

}

int main(){

	scanf("%lld%lld%lld",&B,&D,&N);

	if(!N){

		puts("1");

		return 0;

	}

	x.a[0][0]=0;

	x.a[1][0]=1;

	x.a[1][1]=B;

	x.a[0][1]=(D-ksc(B,B))>>2;

	solve();

	return 0;

}

巴特西