首页 > 其他 > 详细

【luogu P1939 【模板】矩阵加速(数列)】 题解

时间:2018-09-14 22:31:09      阅读:44      评论:0      收藏:0      [点我收藏+]

标签:数列   cout   spa   space   clas   fin   algo   ()   题解   

题目链接:https://www.luogu.org/problemnew/show/P1939

对于矩阵推序列的式子:

由题意知:

f[x+1] =1f[x] + 0f[x-1] + 1f[x-2]
f[x] = 1
f[x] + 0f[x-1] + 0f[x-2]
f[x-1] = 0f[x] + 1f[x-1] + 0*f[x-2]

所以矩阵初项的系数:
1 1 0
0 0 1
1 0 0

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn = 110;
const int mod = 1000000007;
struct Matrix{
    ll m[maxn][maxn];
}A, E, Ans;
ll n, q[maxn];
Matrix mul(Matrix A, Matrix B)
{
    Matrix C;
    for(int i = 1; i <= 3; i++)
        for(int j = 1; j <= 3; j++)
        {
            C.m[i][j] = 0;
            for(int k = 1; k <= 3; k++)
                C.m[i][j] = (C.m[i][j] + A.m[i][k] * B.m[k][j] % mod) % mod;
        }
    return C;       
}
Matrix qpow(Matrix A, ll k)
{
    Matrix S = E;
    while(k)
    {
        if(k & 1) S = mul(S, A);
        A = mul(A, A);
        k = k >> 1;
    }
    return S;
}
int main()
{
    cin>>n;
    E.m[2][2] = 1;
    E.m[1][1] = 1;
    E.m[3][3] = 1;
    A.m[1][1] = 1;
    A.m[1][2] = 1;
    A.m[2][3] = 1;
    A.m[3][1] = 1;
    
    for(int i = 1; i <= n; i++)
    {
        ll k;
        cin>>k;
        Ans = qpow(A, k);
        cout<<Ans.m[1][2]<<endl;
    }
    return 0;
}

【luogu P1939 【模板】矩阵加速(数列)】 题解

标签:数列   cout   spa   space   clas   fin   algo   ()   题解   

原文:https://www.cnblogs.com/MisakaAzusa/p/9648991.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号