【题解】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)\times f(y)-f(x-y)$

于是得到递推式:

$f(x)=f(1)\times 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 '\n'

#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;

}

巴特西

【题解】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)\times f(y)-f(x-y)\)

于是得到递推式:

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

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

最新文章

热门文章