程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4686 Arc of Dream(矩陣快速冪)

HDU 4686 Arc of Dream(矩陣快速冪)

編輯：C++入門知識

HDU 4686 Arc of Dream(矩陣快速冪)

題目地址：HDU 4686

我去。。因為忘記把函數裡的k定義成64位的，導致TLE了一晚上。。。暈。。

這題沒什麼技巧，就是根據公式構造就行。

代碼如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define LL __int64
const LL mod=1e9+7;
struct matrix
{
    LL ma[8][8];
} init, res;
matrix Mult(matrix x, matrix y)
{
    int i, j, k;
    matrix tmp;
    memset(tmp.ma,0,sizeof(tmp.ma));
    for(i=0; i<7; i++)
    {
        for(k=0; k<7; k++)
        {
            for(j=0; j<7; j++)
            {
                tmp.ma[i][j]=(tmp.ma[i][j]+x.ma[i][k]*y.ma[k][j])%mod;
            }
        }
    }
    return tmp;
}
matrix Pow(matrix x, LL k)
{
    matrix tmp;
    int i, j;
    for(i=0; i<7; i++) for(j=0; j<7; j++) tmp.ma[i][j]=(i==j);
    while(k)
    {
        if(k&1) tmp=Mult(tmp,x);
        x=Mult(x,x);
        k>>=1;
    }
    return tmp;
}
int main()
{
    LL k, ax, ay, bx, by, i, j, a0, b0;
    while(scanf("%I64d",&k)!=EOF)
    {
        scanf("%I64d%I64d%I64d%I64d%I64d%I64d",&a0,&ax,&ay,&b0,&bx,&by);
        if(k==0)
        {
            puts("0");
            continue ;
        }
        memset(init.ma,0,sizeof(init.ma));
        init.ma[0][0]=ax; init.ma[0][4]=1;
        init.ma[1][1]=bx; init.ma[1][5]=1;
        init.ma[2][0]=(ax*by)%mod;init.ma[2][1]=(ay*bx)%mod;init.ma[2][2]=(ax*bx)%mod;init.ma[2][3]=1;
        init.ma[3][3]=1;
        init.ma[4][4]=1;
        init.ma[5][5]=1;
        init.ma[6][0]=(ax*by)%mod;init.ma[6][1]=(ay*bx)%mod;init.ma[6][2]=(ax*bx)%mod;init.ma[6][3]=1;init.ma[6][6]=1;
        res=Pow(init,k-1);
        LL ans;
        ans=(a0*res.ma[6][0]+b0*res.ma[6][1]+a0*b0%mod*res.ma[6][2]+ay*by%mod*res.ma[6][3]+ay*res.ma[6][4]+by*res.ma[6][5]+a0*b0%mod*res.ma[6][6])%mod;
        printf("%I64d\n",ans);
    }
    return 0;
}