HDU-6470 矩阵快速幂

Myth丶恋晨 2022-03-02 13:44 392阅读 0赞

# 题目衔接：[http://acm.hdu.edu.cn/showproblem.php?pid=6470][http_acm.hdu.edu.cn_showproblem.php_pid_6470] #

# Count #

**Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)  
Total Submission(s): 565    Accepted Submission(s): 226**

**Problem Description**

Farmer John有n头奶牛.  
某天奶牛想要数一数有多少头奶牛,以一种特殊的方式:  
第一头奶牛为1号,第二头奶牛为2号,第三头奶牛之后,假如当前奶牛是第n头,那么他的编号就是2倍的第n-2头奶牛的编号加上第n-1头奶牛的编号再加上自己当前的n的三次方为自己的编号.  
现在Farmer John想知道,第n头奶牛的编号是多少,估计答案会很大,你只要输出答案对于123456789取模.

**Input**

第一行输入一个T,表示有T组样例  
接下来T行,每行有一个正整数n,表示有n头奶牛 (n>=3)  
其中，T=10^4,n<=10^18

**Output**

共T行,每行一个正整数表示所求的答案

**Sample Input**

5 3 6 9 12 15

**Sample Output**

31 700 7486 64651 527023

**Source**

[“字节跳动-文远知行杯”广东工业大学第十四届程序设计竞赛][-]

题目大意就不在描述了，思路：看到数据范围，1e18非常大的一个数，暴力肯定不行，打表也有困难，题目中也直接给了公式：F(n)=2F(n-2)+F(n-1)+n^3

所以我们用矩阵快速幂来做；

首先构造矩阵得到转移矩阵

1 2 1 3 3 1

1 0 0 0 0 0

0 0 1 3 3 1

0 0 0 1 2 1

0 0 0 0 1 1

0 0 0 0 0 1

初始矩阵为：2 1 8 4 2 1

所以套用模板得：

代码：

#include<map>
    #include<set>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define ll  long long
    #define inf 0x3f3f3f3
    #define esp 1e-8
    #define bug {printf("mmp\n");}
    #define mm(a,b) memset(a,b,sizeof(a))
    const int maxn=6;
    const double pi=acos(-1.0);
    const int N=1e9+100;
    const int mod=123456789;
    
    struct node
    {
        ll A[maxn][maxn];
    } r;
    node init=
    {
        1,2,1,3,3,1,
        1,0,0,0,0,0,
        0,0,1,3,3,1,
        0,0,0,1,2,1,
        0,0,0,0,1,1,
        0,0,0,0,0,1
    };
    node matrix(node m,node r)
    {
        node c;
        for(int i=0; i<maxn; i++)
        {
            for(int j=0; j<maxn; j++)
            {
                c.A[i][j]=0;
                for(int k=0; k<maxn; k++)
                {
                    c.A[i][j]=(c.A[i][j]+(m.A[i][k]*r.A[k][j])%mod)%mod;
                }
            }
        }
        return c;
    }
    node powmi(node a,ll k)
    {
        node res;
        memset(res.A,0,sizeof(res.A));
        for(int i=0; i<maxn; i++)
            res.A[i][i]=1;
        while(k)
        {
            if(k&1)
                res=matrix(res,a);
            k>>=1;
            a=matrix(a,a);
        }
        return res;
    }
    
    int main()
    {
        int test;
        scanf("%d",&test);
        while(test--)
        {
            ll n;
            scanf("%lld",&n);
            node aa=powmi(init,n-2);
            ll res[]= {2,1,8,4,2,1},sum=0;
            for(int i=0; i<maxn; i++)
            {
                sum=(sum+(aa.A[0][i]*res[i])%mod)%mod;
            }
            printf("%lld\n",sum);
    
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_6470]: http://acm.hdu.edu.cn/showproblem.php?pid=6470
[-]: http://acm.hdu.edu.cn/search.php?field=problem&key=%A1%B0%D7%D6%BD%DA%CC%F8%B6%AF-%CE%C4%D4%B6%D6%AA%D0%D0%B1%AD%A1%B1%B9%E3%B6%AB%B9%A4%D2%B5%B4%F3%D1%A7%B5%DA%CA%AE%CB%C4%BD%EC%B3%CC%D0%F2%C9%E8%BC%C6%BE%BA%C8%FC&source=1&searchmode=source