欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

voj 1067 经典矩阵7 递推+矩阵快速幂

程序员文章站 2024-03-24 15:57:04
...

题目:https://vijos.org/p/1067

感觉网上其他题解有点奇怪

这个图写错了,矩阵写到前面去。

voj 1067 经典矩阵7 递推+矩阵快速幂

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
const ll mod = 7777777;
const int maxn=11;

struct matrix{
    ll arr[maxn][maxn];
    matrix operator*(matrix b){
        matrix ans;
        ll tmp;
        for(int i=0; i<maxn; i++)
        for(int j=0; j<maxn; j++){
            ans.arr[i][j] = 0;
            for(int k=0; k<maxn; k++){
                tmp = (arr[i][k]*b.arr[k][j])%mod;
                ans.arr[i][j] = (ans.arr[i][j] + tmp)%mod;
            }
        }
        return ans;
    }
};
matrix quick_pow(matrix a,ll N){
    matrix ans;
    memset(ans.arr,0,sizeof(ans.arr));
    for(int i=0; i<maxn; i++)
        ans.arr[i][i] = 1;
    while(N){
        if(N&1)
            ans = ans*a;
        a = a*a;
        N /= 2;;
    }
    return ans;
}

int main(){
    ll k,n,tmp[11];
    matrix a;
    scanf("%lld%lld",&k,&n);
    memset(a.arr,0,sizeof(a.arr));
    for(int i=0;i<k;i++){
        if(i!=k-1)
            a.arr[i][i+1]=1;
        else
            for(int j=0;j<k;j++)
                a.arr[i][j]=1;
    }
    for(int i=0;i<k;i++)
        tmp[i]=pow(2,i);
    a=quick_pow(a,n-k);
    ll ans=0;
    for(int i=0;i<k;i++){
        //cout<<tmp[i]<<" ";
        ans+=a.arr[k-1][i]*tmp[i];
        ans%=mod;
    }
    printf("%lld\n",ans);
    /*for(int i=0;i<k;i++){
        for(int j=0;j<k;j++){
            printf("%lld ",a.arr[i][j]);
        }
        cout<<endl;
    }*/
    return 0;
}