/ Randle /

记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 5ms 760.0 KiB
#2 Accepted 5ms 744.0 KiB
#3 Accepted 4ms 748.0 KiB
#4 Accepted 6ms 736.0 KiB
#5 Accepted 6ms 728.0 KiB
#6 Accepted 6ms 768.0 KiB
#7 Accepted 6ms 768.0 KiB
#8 Accepted 6ms 752.0 KiB
#9 Accepted 5ms 760.0 KiB
#10 Accepted 5ms 768.0 KiB

代码

#include<cstdio>  
#include<iostream>
#include<cstring>  
#include<algorithm>  
#define MAXN 100  
#define ll long long  
const ll mod=1e9+7;
using namespace std;  
struct Matrix  
{  
    ll a[MAXN][MAXN];  
    int r, c;
};  
Matrix ori, res;
void init()
{  
    memset(res.a, 0, sizeof(res.a));  
    res.r = 2; res.c = 2;  
    for(int i = 1; i <= 2; i++)
        res.a[i][i] = 1;  
    ori.r = 2; ori.c = 2;  
    ori.a[1][1] = ori.a[1][2] = ori.a[2][1] = 1;  
    ori.a[2][2] = 0;  
}  
Matrix multi(Matrix x, Matrix y)  
{  
    Matrix z;  
    memset(z.a, 0, sizeof(z.a));  
    z.r = x.r, z.c = y.c;
    for(int i = 1; i <= x.r; i++)
    {  
        for(int k = 1; k <= x.c; k++) 
        {  
            if(x.a[i][k] == 0) continue;
            for(int j = 1; j<= y.c; j++)
                z.a[i][j] = (z.a[i][j] + (x.a[i][k] * y.a[k][j]) % mod) % mod;  
        }  
    }  
    return z;  
}  
void Matrix_mod(int n)  
{  
    while(n)
    {  
        if(n & 1)  
            res = multi(ori, res);  
        ori = multi(ori, ori);  
        n >>= 1;  
    }  
    printf("%lld\n", res.a[1][2] % mod);  
}  
int main()  
{  
    int N;  
    cin>>N;
    N++;
    init();
    Matrix_mod(N);  
    
    return 0;  
}  

信息

递交者
类型
递交
题目
上楼梯(数据原创)
题目数据
下载
语言
C++
递交时间
2017-10-21 23:01:04
评测时间
2017-10-21 23:01:04
评测机
分数
100
总耗时
57ms
峰值内存
768.0 KiB