「题解」「JLOI2015」有意义的字符串 jxamfe

JLOI2015 Day 1 T1,一道有意思的数学题。

题目链接:Luogu P3263BZOJ 4002LibreOJ 2106、JLOI2015 D1T1。

题目

题目描述

B 君有两个好朋友,他们叫宁宁和冉冉。有一天,冉冉遇到了一个有趣的题目:输入 \(b,d,n\),求
\[\left\lfloor\left(\frac{b-\sqrt{d}}{2}\right)^n\right\rfloor\bmod{7528443412579576937}\]

数据范围

其中  \(0<b^2\leq d<(b+1)^2\leq 10^{18},n\leq 10^{18}\),并且 \(b\bmod 2=1,d\bmod 4=1\)。

时空限制

未完待续。

题解

思路

考虑两个数 \(\frac{b-\sqrt{d}}{2},\frac{b+\sqrt{d}}{2}\),那么我们不难得出,它们是下面的方程的两个解
\[x^2-bx+\frac{b^2-d}{4}=0\]

移项
\[x^2=bx-\frac{b^2-d}{4}\]

两边同乘 \(x^{n-2}\)
\[x^n=bx^{n-1}-\frac{b^2-d}{4}x^{n-2}\]

根据特征方程可知
\[f _ n=bf _ {n-1}+\frac{b^2-d}{4}f _ {n-2}\]

我们可以用矩阵快速幂优化线性递推解决求 \(f _ n\) 的问题。

显然根据上面的推导和数据范围中的提示可知。
\[
\texttt{ans}=\begin{cases}
f _ n-1&,n\bmod 2=0\wedge d\ne b^2\\
f _ n&,\text{otherwise}
\end{cases}
\]

这种做法的时间复杂度为 \(\Theta(|S|^3\log _ 2n)\)。其中 \(|S|=2\)。

代码

记得不要爆数据范围了。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef unsigned long long ull;

const ull p=7528443412579576937ull;

ull b,d,n;

inline ull add(reg ull a,reg ull b){
	reg ull sum=a+b;
	return sum>=p?sum-p:sum;
}

inline ull mul(reg ull a,reg ull b){
	reg ull res=0;
	while(b){
		if(b&1)
			res=add(res,a);
		a=add(a,a);
		b>>=1;
	}
	return res;
}

inline ull pow(reg ull x,reg ull exp){
	reg ull res=1;
	while(exp){
		if(exp&1)
			res=mul(res,x);
		x=mul(x,x);
		exp>>=1;
	}
	return res;
}

const int MAXSIZE=2;

struct Matrix{
	ull unit[MAXSIZE][MAXSIZE];
	inline Matrix(reg ull x=0){
		for(reg int i=0;i<MAXSIZE;++i)
			for(reg int j=0;j<MAXSIZE;++j)
				unit[i][j]=(i==j)?x:0;
		return;
	}
	inline Matrix operator*(const Matrix& a){
		Matrix res(0);
		reg ull r;
		for(reg int i=0;i<MAXSIZE;++i)
			for(reg int k=0;k<MAXSIZE;++k){
				r=unit[i][k];
				for(reg int j=0;j<MAXSIZE;++j)
					res.unit[i][j]=add(res.unit[i][j],mul(r,a.unit[k][j]));
			}
		return res;
	}
	inline Matrix operator^(reg ull exp){
		Matrix res(1),x=*this;
		while(exp){
			if(exp&1)
				res=res*x;
			x=x*x;
			exp>>=1;
		}
		return res;
	}
	inline ull* operator[](reg int i){
		return unit[i];
	}
};

Matrix f,base;

int main(void){
	scanf("%llu%llu%llu",&b,&d,&n);
	if(n==0)
		puts("1");
	else{
		reg ull A=b,B=add(d>>2,p-mul((b+1ull)>>1ull,(b-1ull)>>1ull));
		f[0][0]=A,f[0][1]=1,f[1][0]=B;
		base[0][0]=b,base[0][1]=2;
		Matrix ans(0);
		ans=base*(f^(n-1));
		if((!(n&1))&&d!=mul(b,b))
			printf("%llu\n",add(ans[0][0],p-1));
		else
			printf("%llu\n",ans[0][0]%p);
	}
	return 0;
}