[BZOJ 2326][HNOI 2011]數學作業(矩陣快速冪)

[BZOJ 2326][HNOI 2011]數學作業(矩陣快速冪)

蒟蒻線性代數太爛了。。。這個逼題居然卡了半天才做出來，弱的不行啊。。。

矩陣快速冪，把n這個len位數拆成len次分段快速冪就可以了。

注意取模的數字m<=1e9，所以矩陣乘法運算時要先對乘數取模，防止中間運算結果太大溢出，坑爹啊

代碼：

#include 
#include 
#include 
#include 
#include 

#define MAXN 4

using namespace std;

typedef long long int LL;

int mod;

struct matrix
{
    LL p[MAXN][MAXN];
}ans,tmp;

matrix operator*(matrix a,matrix b)
{
    matrix c;
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
        {
            c.p[i][j]=0;
            for(int k=1;k<=3;k++)
                c.p[i][j]=(c.p[i][j]+((a.p[i][k]%mod)*(b.p[k][j]%mod))%mod)%mod;
        }
    return c;
}

void cal(LL t,LL last) //從last-t/10計算到last
{
    memset(tmp.p,0,sizeof(tmp.p));
    tmp.p[1][1]=t;
    tmp.p[2][1]=tmp.p[3][1]=tmp.p[2][2]=tmp.p[3][2]=tmp.p[3][3]=1;
    LL y=last-t/10+1;
    while(y)
    {
        if(y&1) ans=ans*tmp;
        tmp=tmp*tmp;
        y>>=1;
    }
}

int main()
{
    for(int i=1;i<=3;i++)
        ans.p[i][i]=1;
    LL n;
    scanf("%lld%lld",&n,&mod);
    LL t=10;
    while(n>=t)
    {
        cal(t,t-1);
        t*=10;
    }
    cal(t,n);
    printf("%lld\n",ans.p[3][1]);
    return 0;
}