题解：P9777 [HUSTFC 2023] Fujisaki 讨厌数学
damnM3bro
·
·
题解
题意
给出 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}
### 代码
```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;
}
```