Submission #3410460

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
ll n;
struct MAR{ll a[2][2];};
MAR mul(MAR x,MAR y){
    MAR temp;
    memset(temp.a,0,sizeof(temp.a));
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++){
                temp.a[i][j]=temp.a[i][j]+(x.a[i][k]*y.a[k][j]);
            }
    return temp;		
}
ll MAR_pow(ll x){
    MAR c,s;
    c.a[0][0]=c.a[0][1]=c.a[1][0]=1;c.a[1][1]=0;
    memset(s.a,0,sizeof(s.a));
    s.a[0][0]=s.a[0][1]=1;
    while(x){
        if(x&1)	s=mul(s,c);
        c=mul(c,c);
        x=(x>>1);
    }
    return s.a[0][0];
}
int main(){
    cin>>n;
    n++; 
    if(n==1)	cout<<"1";
    else cout<<MAR_pow(n-2);
    return 0;
}

Submission Info

Judge Result