[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
",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;
}