*行列の高速べき乗(フィボナッチ数列テンプレート)
4074 ワード
2017/5/31,DCDCBigBig
マトリックス高速べき乗
// 100000007
#include
#include
#include
#include
#define MOD 100000007
using namespace std;
typedef long long ll;
struct sq{
ll sq[2][2];
void mes(){
memset(sq,0,sizeof(sq));
}
};
sq operator *(sq a,sq b){
sq tmp;
tmp.mes();
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
for(int k=0;k<2;k++){
tmp.sq[i][j]=(tmp.sq[i][j]+a.sq[i][k]*b.sq[k][j])%MOD;
}
}
}
return tmp;
}
ll fi(int n){
sq ans,m;
ans.mes();
m.mes();
m.sq[0][0]=m.sq[0][1]=m.sq[1][0]=1;
m.sq[1][1]=0;
ans.sq[0][0]=ans.sq[1][1]=1;
ans.sq[0][1]=ans.sq[1][0]=0;
while(n){
if(n&1){
ans=ans*m;
}
m=m*m;
n>>=1;
}
return ans.sq[0][1]%MOD;
}
int main(){
int n;
scanf("%d",&n);
printf("%lld",fi(n));
return 0;
}
病気