FZU - 1683(矩阵快速幂)

朴灿烈づ我的快乐病毒、 2022-06-09 00:56 105阅读 0赞

问题描述:

已知 F（n）=3 \* F（n-1）+2 \* F（n-2）+7 \* F（n-3），n>=3，其中F（0）=1，F（1）=3，F（2）=5，对于给定的每个n，输出F（0）+ F（1）+ …… + F（n） mod 2009。

Input

第一行是一整数m，代表总共有m个cases。

Output

对于每个case，输出一行。格式见样例，冒号后有一个空格。

Sample Input

2
    3
    6

Sample Output

Case 1: 37
    Case 2: 313

题目题意：题目个我们一个数n，让我们根据那个表达式求出 f(0)+f(1)+...f(n) % 2009.

题目分析：很明显的要用到矩阵快速幂来加速推导过程，快速的求出结果。

我们构建如下的矩阵:

3   2   7   0                f(n-1)            f(n)

1   0   0   0      \*         f(n-2)    =     f(n-1)

0   1   0   0                f(n-3)            f(n-2)

3   2   7   1                sum              sum'

矩阵构造了，就可以直接用模板了

我的代码写得并不好看，可以根据自己的喜好，来写代码。

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cstdio>
    const int inf=2009;
    using namespace std;
    
    struct matrix//构建矩阵,我喜欢把矩阵乘法写成重载函数，也可以写成普通函数
    {
        int f[5][5];
        matrix operator *(const  matrix &a) const {
          struct matrix res;
           for (int i=1;i<=4;i++) {
            for (int j=1;j<=4;j++) {
                res.f[i][j]=0;
                for (int k=1;k<=4;k++)
                    res.f[i][j]=(res.f[i][j]+(*this).f[i][k]*a.f[k][j])%inf;
                res.f[i][j]=res.f[i][j]%inf;
            }
           }
           return res;
        }
    }a,b;
    
    struct matrix fast_pow(struct matrix aa,int k)//快速幂
    {
        struct matrix ans;
        memset (&ans.f,0,sizeof (ans.f));
        for (int i=1;i<=4;i++)
            ans.f[i][i]=1;
        while (k) {
            if (k&1)
                ans=ans*aa;
            aa=aa*aa;
            k>>=1;
        }
        return ans;
    };
    void init()//预处理矩阵，把那个常数矩阵处理一下
    {
        a.f[1][1]=5,a.f[2][1]=3,a.f[3][1]=1,a.f[4][1]=9;
        b.f[1][1]=3,b.f[1][2]=2,b.f[1][3]=7;
        b.f[2][1]=1;
        b.f[3][2]=1;
        b.f[4][1]=3,b.f[4][2]=2,b.f[4][3]=7,b.f[4][4]=1;
    
    }
    int main()
    {
        int t,icase=1;
        scanf("%d",&t);
        while (t--) {
            int n;
            scanf("%d",&n);
            init();
            if (n==0) {  printf("Case %d: %d\n",icase++,1); continue;}
            if (n==1) {  printf("Case %d: %d\n",icase++,4); continue;}
            if (n==2) {  printf("Case %d: %d\n",icase++,9); continue;}
            n-=2;
            struct matrix cur, ans;
            cur=b;
            cur=fast_pow(cur,n);
            ans=cur*a;
            printf("Case %d: %d\n",icase++,ans.f[4][1]);
        }
        return 0;
    }