HDU4686[矩陣快速冪]

只能說自己以前做的那個矩陣快速冪太弱了，或者推的還不夠。

這道題把f(i),s(i),a(i),b(i)都合在一塊了，一個5*5的矩陣。

另外，反正在hdu就用%I64d，別管別的了。 keng...

我的paw,multiply模板肯定沒錯，連續的WA是坑在__int64上。

練習的題目太少，推敲涉及比較多的變量，贊一個

 
#include <iostream>   
#include <cstdio>   
#include <cstring>   
using namespace std;  
  
typedef __int64 LL;  
const LL maxn=1e18+7;  
const LL mod=1000000007;  
  
typedef struct M  
{  
    LL x[6][6];  
}mat;  
  
struct M multiply(struct M a,struct M b)  
{  
    struct M ret;  
    for(int i = 0;i<5;i++)  
    {  
        for(int j = 0;j <5;j++)  
        {  
            LL tem = 0;  
            for(int k = 0;k < 5;k++)  
                tem = (tem+a.x[i][k]*b.x[k][j])%mod;  
            ret.x[i][j] = tem%mod;//這地方取模注意一下.   
        }  
    }  
    return ret;  
}  
  
struct M paw(struct M a,long long t)  
{  
    if(t==1)  
        return a;  
    else  
    {  
        struct M b=paw(a,t/2);  
        if(t&1)  
        {  
            return multiply(multiply(b,b),a);  
        }  
        else  
            return multiply(b,b);  
    }  
}  
  
mat org,add;  
  
int main()  
{  
    LL n,a0,ax,ay;  
    LL b0,bx,by;  
    while(scanf("%I64d",&n)!=EOF)  
    {  
        scanf("%I64d%I64d%I64d",&a0,&ax,&ay);  
        scanf("%I64d%I64d%I64d",&b0,&bx,&by);  
        if(n==0) {printf("0\n");continue;}  
        memset(org.x,0,sizeof(org.x));  
        memset(add.x,0,sizeof(add.x));  
  
        add.x[0][0]=1; add.x[0][1]=0;         add.x[0][2]=0;      add.x[0][3]=0;      add.x[0][4]=0;  
        add.x[1][0]=1; add.x[1][1]=ax*bx%mod; add.x[1][2]=0;      add.x[1][3]=0;      add.x[1][4]=0;  
        add.x[2][0]=0; add.x[2][1]=ax*by%mod; add.x[2][2]=ax%mod; add.x[2][3]=0;      add.x[2][4]=0;  
        add.x[3][0]=0; add.x[3][1]=ay*bx%mod; add.x[3][2]=0;      add.x[3][3]=bx%mod; add.x[3][4]=0;  
        add.x[4][0]=0; add.x[4][1]=ay*by%mod; add.x[4][2]=ay%mod; add.x[4][3]=by%mod; add.x[4][4]=1;  
  
        org.x[0][0]=a0*b0%mod; org.x[0][1]=(((a0*ax+ay)%mod)*((b0*bx+by)%mod))%mod;  
        org.x[0][2]=(a0*ax+ay)%mod; org.x[0][3]=(b0*bx+by)%mod; org.x[0][4]=1;  
  
        mat ans;  
        if(n==1) ans=org;  
        else  
        {  
            ans=multiply(org,paw(add,n-1));  
        }  
        printf("%I64d\n",ans.x[0][0]%mod);  
     }  
    return 0;  
}  

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

typedef __int64 LL;
const LL maxn=1e18+7;
const LL mod=1000000007;

typedef struct M
{
    LL x[6][6];
}mat;

struct M multiply(struct M a,struct M b)
{
    struct M ret;
    for(int i = 0;i<5;i++)
    {
        for(int j = 0;j <5;j++)
        {
            LL tem = 0;
            for(int k = 0;k < 5;k++)
                tem = (tem+a.x[i][k]*b.x[k][j])%mod;
            ret.x[i][j] = tem%mod;//這地方取模注意一下.
        }
    }
    return ret;
}

struct M paw(struct M a,long long t)
{
    if(t==1)
        return a;
    else
    {
        struct M b=paw(a,t/2);
        if(t&1)
        {
            return multiply(multiply(b,b),a);
        }
        else
            return multiply(b,b);
    }
}

mat org,add;

int main()
{
    LL n,a0,ax,ay;
    LL b0,bx,by;
    while(scanf("%I64d",&n)!=EOF)
    {
        scanf("%I64d%I64d%I64d",&a0,&ax,&ay);
        scanf("%I64d%I64d%I64d",&b0,&bx,&by);
        if(n==0) {printf("0\n");continue;}
        memset(org.x,0,sizeof(org.x));
        memset(add.x,0,sizeof(add.x));

        add.x[0][0]=1; add.x[0][1]=0;         add.x[0][2]=0;      add.x[0][3]=0;      add.x[0][4]=0;
        add.x[1][0]=1; add.x[1][1]=ax*bx%mod; add.x[1][2]=0;      add.x[1][3]=0;      add.x[1][4]=0;
        add.x[2][0]=0; add.x[2][1]=ax*by%mod; add.x[2][2]=ax%mod; add.x[2][3]=0;      add.x[2][4]=0;
        add.x[3][0]=0; add.x[3][1]=ay*bx%mod; add.x[3][2]=0;      add.x[3][3]=bx%mod; add.x[3][4]=0;
        add.x[4][0]=0; add.x[4][1]=ay*by%mod; add.x[4][2]=ay%mod; add.x[4][3]=by%mod; add.x[4][4]=1;

        org.x[0][0]=a0*b0%mod; org.x[0][1]=(((a0*ax+ay)%mod)*((b0*bx+by)%mod))%mod;
        org.x[0][2]=(a0*ax+ay)%mod; org.x[0][3]=(b0*bx+by)%mod; org.x[0][4]=1;

        mat ans;
        if(n==1) ans=org;
        else
        {
            ans=multiply(org,paw(add,n-1));
        }
        printf("%I64d\n",ans.x[0][0]%mod);
     }
    return 0;
}