记录编号	437938	评测结果	AAAAAAAAAA
题目名称	斐波那契平方和	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2017-08-14 21:35:57	内存使用	0.32 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
 
#define MOD (1000000007)
typedef long long LL;
 
inline void Pow(LL N);
 
LL res[2][2] = {{1, 0},
                {0, 1}};
LL fib[2] = {0, 1};
LL tmp[2][2];
LL q[2][2] = {{0, 1},
              {1, 1}};
LL N;
 
int main() { 
#ifndef LOCAL
    freopen("fibsqr.in", "r", stdin);
    freopen("fibsqr.out", "w", stdout);
#endif
    scanf("%lld", &N);
    Pow(N);
    memset(tmp, 0x00, sizeof(tmp));
    for(int i = 0; i < 2; ++i) 
        for(int j = 0; j < 2; ++j) 
            (tmp[0][i] += fib[j] * res[j][i]) %= MOD;
    printf("%lld", tmp[0][0] * tmp[0][1] % MOD);
    return 0;
}
 
inline void Pow(LL N) { 
    while(N) { 
        if(N & 1) { 
            memset(tmp, 0x00, sizeof(tmp));
            for(char i = 0; i < 2; ++i) 
                for(char j = 0; j < 2; ++j) 
                    for(char k = 0; k < 2; ++k) 
                        (tmp[i][j] += res[i][k] * q[k][j]) %= MOD;
            for(char i = 0; i < 2; ++i) 
                for(char j = 0; j < 2; ++j) 
                    res[i][j] = tmp[i][j];
        }
        memset(tmp, 0x00, sizeof(tmp));
        for(char i = 0; i < 2; ++i) 
            for(char j = 0; j < 2; ++j) 
                for(char k = 0; k < 2; ++k) 
                    (tmp[i][j] += q[i][k] * q[k][j]) %= MOD;
        for(char i = 0; i < 2; ++i) 
            for(char j = 0; j < 2; ++j) 
                q[i][j] = tmp[i][j];
        N >>= 1;
    }
    return ;
}