[INFOR] 14 費氏數列問題

題目連結：https://oj.infor.org/problems/14
　　矩陣快速冪。

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long lld;
const lld mmod = 1000000007ll;
lld m,n;
lld m1[110][110], m2[110][110];
lld ans[110][110], tp[110][110];
inline void matrixtime(lld a[][110],lld b[][110],lld c[][110])
{
    for(int i = 0; i < m; i++)
        for(int j = 0; j < m; j++)
        {
            c[i][j] = 0;
            for(int k = 0; k < m; k++)
            {
                c[i][j] += a[i][k]*b[k][j];
                c[i][j] %= mmod;
            }
        }
}
inline void qpow(lld n)
{
    for(int i = 0; i < m; i++)
        for(int j = 0; j < m; j++)
            ans[i][j] = (i==j);
    bool flag = false;
    while(n)
    {
        if(n&1)
        {
            matrixtime(ans,(!flag)?m1:m2,tp);
            swap(tp,ans);
        }
        if(!flag) matrixtime(m1,m1,m2);
        else matrixtime(m2,m2,m1);
        flag ^= 1;
        n >>= 1;
    }
}
int main()
{
    scanf("%lld %lld",&n,&m);
    for(int i = 0; i < m; i++)
    {
        if(i+1 < m) m1[i][i+1] = 1;
        scanf("%lld",&m1[i][0]);
    }
    qpow(n-m);
    lld anw = 0;
    for(int i = 0; i < m; i++)
    {
        anw += ans[i][0];
        anw %= mmod;
    }
    printf("%lld",anw);
}