多校 4686 Arc of Dream hdu 矩阵解

构造矩阵如下：

Ai*bi        AX*BX    AX*BY   AY*BX    AY*BY      0      a(i-1)*b(i-1)

Ai            0       AX       0       AY         0      a(i-1)

Bi            0       0        BX      BY         0      b(i-1)

1             0       0        0       1          0      1

Sum(i)        AX*BX   AX*BY   AY*BX    AY*BY      1      sum(i-1)

Sum(i) 表示i项和,sum(i)=sum(i-1)+ai*bi;

求第n次的结果,直接对矩阵作n-1次，利用矩阵快速幂,时间复杂度为10*logn~logn

注意取模爆范围和对n=0特判。

#include <stdio.h>

#include <cstring>

#include <algorithm>

#include <vector>

#include <cmath>

using namespace std;

typedef unsigned long long ll;

int mod=1000000007;

ll tmp[5][5],a[5][5],b[5][5];

void mul(ll a[][5],ll b[][5])

{

    for(int i=0; i<5; i++)

        for(int j=0; j<5; j++)

        {

            tmp[i][j]=0;

            for(int k=0; k<5; k++)

            {

                tmp[i][j]+=(a[i][k]%mod)*(b[k][j]%mod);

                tmp[i][j]%=mod;

            }

        }

    memcpy(a,tmp,sizeof(tmp));

}

void pow(ll a[][5],ll b[][5],ll n)

{

    memset(a,0,sizeof(a));

    for(int i=0; i<5; i++) a[i][i]=1;

    while(n)

    {

        if(n&1) mul(a,b);

        mul(b,b);

        n>>=1;

    }

}

int main()

{

    ll a0,ax,ay,b0,bx,by;

    ll k;

    while(scanf("%I64u",&k)==1)

    {

        memset(b,0,sizeof(b));

        memset(a,0,sizeof(a));

        scanf("%I64u%I64u%I64u%I64u%I64u%I64u",&a0,&ax,&ay,&b0,&bx,&by);

        if(k==0)

        {

            printf("0\n");

            continue;

        }

        b[0][0]=((ax%mod)*(bx%mod))%mod;

        b[0][1]=((ax%mod)*(by%mod))%mod;

        b[0][2]=((ay%mod)*(bx%mod))%mod;

        b[0][3]=((ay%mod)*(by%mod))%mod;

        b[3][3]=1;

        b[1][1]=ax%mod;

        b[1][3]=ay%mod;

        b[2][2]=bx%mod;

        b[2][3]=by%mod;

        b[4][0]=((ax%mod)*(bx%mod))%mod;

        b[4][1]=((ax%mod)*(by%mod))%mod;

        b[4][2]=((ay%mod)*(bx%mod))%mod;

        b[4][3]=((ay%mod)*(by%mod))%mod;

        b[4][4]=1;

        pow(a,b,k-1);

        ll ans=0;

        ans+=((((a0%mod)*(b0%mod))%mod)*a[4][0])%mod;

        ans%=mod;

        ans+=((a0%mod)*(a[4][1]%mod))%mod;

        ans%=mod;

        ans+=((b0%mod)*(a[4][2])%mod)%mod;

        ans%=mod;

        ans+=(a[4][3])%mod;

        ans%=mod;

        ans+=(a[4][4]*(a0%mod)*(b0%mod))%mod;

        ans%=mod;

        printf("%I64u\n",ans%mod);

    }

    return 0;

}

巴特西

多校 4686 Arc of Dream hdu 矩阵解

最新文章

热门文章