题解 P3216 【[HNOI2011]数学作业】

龙神哈迪斯 · 2017-07-14 07:31:11 · 题解

/*这个题目其实就是状态转移矩阵并非一成不变的，而是通过输入n的位数变化而变化的，例如，当n在1-9之间时，位数只有一位，当n在10-99之间时，位数就变成了两位，以此类推，先得到它基本的递推式：fi=fi-1*10+i（当n在1-9之间）fi=fi-1*100+i（当n在10-99之间）,因此我们需要用nd来记录n的位数，用k来当做fi-1乘的那个数值。但是用基本递推式肯定会超时的，所以我们就用矩阵乘法来做到快速幂。不会的同学可以去看下快速幂和矩阵快速幂啊（这其实就是背背模板的问题），好了，话不多说，上代码*/

/*先上第一步矩阵用的状态

S（fi,i,1）T（10,0,0 S'(fi+1,i+1,1)

1,1,0 1,1,1）*/

#include<iostream>
using namespace std;
#define ll long long
ll n,now=0,mod;
struct hand//本人习惯来定义这样的结构体
{
    ll s[3][3];
    hand()
    {
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
            {
                s[i][j]=0;
            }
        }

}//快速清零数组

    hand(ll arr[3][3])
    {
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
            {
                s[i][j]=arr[i][j];
            }
        }

}//快速对数组赋值

};
hand operator *(hand A,hand B)//重载乘法运算符，因为矩阵乘法的运算规律并不同于普通的数与数之间的乘法
{
    hand ans;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
                {
                    ans.s[i][j]=(ans.s[i][j]+A.s[i][k]*B.s[k][j])%mod;
                }
    return ans;
}
int main()
{
    cin>>n>>mod;
    hand S;
    hand T;
    S.s[0][1]=S.s[0][2]=1;
    for(ll k=10;now<n;k*=10)
    {
        T.s[1][0]=T.s[1][1]=T.s[2][1]=T.s[2][2]=1;
        T.s[0][1]=T.s[0][2]=T.s[1][2]=T.s[2][0]=0;
        T.s[0][0]=k%mod;//这里对k取mod不能丢 
        ll nd=min(k-1,n)-now;//来运行所有的小于n的一位、两位数··· 
        while(nd)
        {
            if(nd&1)S=S*T;
            T=T*T;
            nd>>=1;
        }
        now=min(k-1,n);//以防超过n值 
    }
    printf("%d",S.s[0][0]);
    return 0;
}