【题解】T54037 最开始

传送门

题目大意：

对于(a+ frac 1{a^{}}=n)求$a^{m}+ frac 1{a^{m}} $，对(10^9+7)取模。

题目做法：

乍看此题，没有思路，但是如果用数学办法推导一下，就知道怎么做了。

记(f(x)=a^x+ frac 1{a^{x}})

显然当((x>=y))时候(f(x+y)=f(x) imes f(y)-f(x-y))

于是得到递推式:

(f(x)=f(1) imes f(x-1)-f(x-2))，矩阵快速幂即可。

关于这个逆元为什么不需要处理，是因为这个拆分的过程中,我们实际上没有进行无效的除法，我们得到的(f(x-y))访问的直接就是那个取模以后的值。

上代码：

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<vector>
#include<set>
#include<map>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<ctime>

using namespace std;


#define TMP template < class ins >
#define endl '
'
#define RP(t,a,b) for(register int t=(a),edd=(b);t<=edd;t++)
#define ERP(t,a) for(register int t=head[(a)];t;t=e[t].nx)
#define DRP(t,a,b) for(register int t=(a),edd=(b);t>=edd;t--)
typedef long long ll;

TMP inline ins qr(ins tag){
    char c=getchar();
    ins x=0;
    int q=0;
    while(c<48||c>57)
	q=c==45?-1:q,c=getchar();
    while(c>=48&&c<=57)
	x=x*10+c-48,c=getchar();
    return q==-1?-x:x;
}
const ll mod=1e9+7;
const int maxn=3;
ll n;
int K;
struct mtx{
    ll data[maxn][maxn];
    mtx(){memset(data,0,sizeof data);}
    inline ll* operator [](int x){
	return data[x];
    }
    inline void unis(){
	RP(t,1,2)
	    data[t][t]=1;
    }
    inline mtx operator *(mtx a){
	mtx temp;
	RP(t,1,2)
	    RP(i,1,2)
	    RP(k,1,2)
	    temp[t][i]=((temp[t][i]+data[t][k]*a[k][i])%mod)%mod;
	return temp;
    }
    inline mtx operator *=(mtx a){
	return (*this)=(*this)*a;
    }
    inline mtx operator ^(int x){
	mtx ans,base=(*this);
	ans.unis();
	while(x){
	    if(x&1)
		ans*=base;
	    base*=base;
	    x>>=1;
	}
	return ans;
    }
    inline mtx operator ^=(int x){
	int p=x;
	return (*this)=(*this)^p;
    }
    inline void print(){
	RP(t,1,2){
	    RP(i,1,2)
		cout<<(data[t][i])%mod<<' ';
	    cout<<endl;
	}
	cout<<endl;
    }
};

int main(){
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    n=qr(1ll);
    K=qr(1);
    mtx qaq;
    qaq[1][1]=n;
    qaq[1][2]=1;
    qaq[2][1]=-1;
    qaq[2][2]=0;
    qaq^=K-1;
    ll ans=((n*qaq[1][1])%mod+(2*qaq[2][1])%mod+mod)%mod;
    cout<<ans<<endl;
    return 0;
}