题解：P9777 [HUSTFC 2023] Fujisaki 讨厌数学

题意

给出

x+\frac{1}{x}(k)

求

x^n+ \frac{1}{x^n}

。

思路

首先可以想到递推。

令

f_i=x^i+ \frac{1}{x^i}

。

考虑转移。

\begin{aligned} f_i&=x^i+ \frac{1}{x^i}&\\ &=x^i+ \frac{1}{x^i}+x^{i-2}+\frac{1}{x^{i-2}}-(x^{i-2}+\frac{1}{x^{i-2}})&\\ &=(x^{i-1}+\frac{1}{x^{i-1}})(x+\frac{1}{x})-(x^{i-2}+\frac{1}{x^{i-2}})&\\ &=k\times f_{i-1}-f_{i-2} \end{aligned}

n\le 10^{18}

，矩阵加速即可。

代码

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int m,k,n;

struct mat{
	int a[3][3];
	void build(){
		for(int i=1;i<=2;++i)
			for(int j=1;j<=2;++j)
				a[i][j]=0;
	}
	mat operator*(const mat x)const{
		mat res;
		res.build();
		for(int i=1;i<=2;++i){
			for(int j=1;j<=2;++j){
				for(int p=1;p<=2;++p){
					res.a[i][j]+=a[i][p]*x.a[p][j]%m;
					res.a[i][j]%=m;
				}
			} 
		} 
		return res;
	}
};

signed main(){
	cin>>m>>k>>n;
	if(n==1){
		cout<<k;
		return 0;
	}
	if(n==0){
		cout<<2;
		return 0;
	}
	mat x;
	x.a[1][1]=0,x.a[1][2]=-1;
	x.a[2][1]=1,x.a[2][2]=k;
	mat res;
	res.build();
	res.a[1][1]=res.a[2][2]=1;
	--n;
	while(n){
		if(n&1)
			res=res*x;
		x=x*x;
		n>>=1;
	}
	cout<<((2*res.a[1][2]+k*res.a[2][2])%m+m)%m;
}

题解：P9777 [HUSTFC 2023] Fujisaki 讨厌数学

文章操作

题意

思路

代码

相关推荐

评论

题解：P9777 [HUSTFC 2023] Fujisaki 讨厌数学