P3216 [HNOI2011]数学作业(矩阵快速幂)

nofind · 2019-08-14 01:55:52 · 题解

题意:https://www.luogu.org/problem/P3216

一开始没有思路,后来发现了递推式:f[n]=f[n-1]*10^k+n(k是n的位数)

想到矩阵加速数列递推,自然就可以写出转移矩阵：

[f[i],i-1,1] * [10^k,0,0]=[f[i+1],i,1]
        [1,1,0]
        [1,1,1]

对10^k分布矩阵乘法即可

code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Mat
{
    ll a[4][4];
    ll* operator[](int i){return a[i];}
    Mat(int x=0){for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)a[i][j]=x;}
    inline void idx(){for(int i=1;i<=3;i++)a[i][i]=1;}
};
ll n,mod;
Mat A(0);
Mat operator *(Mat a,Mat b)
{
    Mat res(0);
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            for(int k=1;k<=3;k++)
                res[i][j]=(res[i][j]+a[i][k]*b[k][j]%mod)%mod;
    return res; 
}   
Mat operator ^(Mat x,ll k)
{
    Mat res(0);res.idx();
    while(k)
    {
        if(k&1)res=res*x;
        x=x*x;k>>=1;
    }
    return res;
}
inline ll read()
{
    char c=getchar();ll res=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
    return res*f;
}
inline void calc(ll base,ll k)
{
    //printf("%lld %lld\n",base,k);
    Mat B(0);
    B[1][1]=base%mod;B[2][1]=B[2][2]=B[3][1]=B[3][2]=B[3][3]=1;
    B=B^k;A=A*B; 
}
int main()
{
    n=read(),mod=read();
    //printf("%lld %lld\n",n,mod);
    A[1][1]=0;A[1][2]=0;A[1][3]=1;//初始为f[0]
    /*
    for(int i=1;i<=3;i++,puts(""))
        for(int j=1;j<=3;j++)
            cout<<A[i][j]<<' ';
    */
    ll base=10;
    while(base<=n)calc(base,base-(base/10)),base*=10;
    //printf("%lld\n",A[1][1]);
    calc(base,n-(base/10)+1);
    printf("%lld",A[1][1]);
    return 0;
}