BZOJ 5082: 弗拉格 矩阵乘法

如果单点而不是求 sigma 的话还是比较好办的.

遇到这种前缀和相减的矩阵乘法可以增设一个 0 使得后面的能先加到前面，然后再算.

这样的话可以使的最后算出的是前缀和相加的形式.

code:

#include <bits/stdc++.h>

#define ll long long

#define mod 1000000007

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

struct data

{

    ll v[9][9];

    data() { memset(v,0,sizeof(v));}

    ll *operator[](int a) { return v[a]; }

    data operator*(data &a)

    {

        data ans;

        int i,j,k;

        for(i=0;i<=8;++i)

            for(j=0;j<=8;++j)

                for(k=0;k<=8;++k)

                    ans[i][j]=(ans[i][j]+v[i][k]*a[k][j]%mod)%mod;

        return ans;

    }

}A,T;

data pow(data x,int y)

{

    data ans;

    int i;

    for(i=0;i<=8;++i) ans[i][i]=1;

    while(y)

    {

        if(y&1) ans=ans*x;

        x=x*x;

        y>>=1;

    }

    return ans;

}

void init()

{

    for(int i=0;i<=8;++i) A[i][0]=1;

    A[1][5]=A[1][7]=1;

    A[2][5]=A[2][7]=1;

    A[3][6]=A[3][8]=1;

    A[4][6]=A[4][8]=1;

    A[5][1]=A[5][3]=1;

    A[6][1]=A[6][3]=1;

    A[7][2]=A[8][4]=1;

}

ll calc(int x)

{

    if(!x) return 0;

    data tmp=pow(A,x-1);

    ll ans=tmp[0][0]*4;

    for(int i=1;i<=8;++i) ans+=tmp[i][0];

    return ans%mod;

}

int main()

{

    // setIO("input");

    int i,j,l,r;

    scanf("%d%d",&l,&r),--l;

    init();

    printf("%lld\n",((calc(r) + calc((r+1)/2) - calc(l) - calc((l+1)/2)) * 500000004 % mod + mod)%mod);

    return 0;

}