[HNOI2011]数学作业 题解

　　这道题看着挺难然而其实看破了也挺容易的。首先N极其的大，几乎要炸掉long long ，所以O(n)的算法一定是扑街了，身为一个脑残志坚的OIer，怎能不想到矩阵快速幂优化呢？ 

　　有趣的是这道题矩阵有很多种，Q某犇有另一种做法，大家也可以去他那看一看。

　　答案矩阵是这样的：

　　　　f[x]   x+1   1

　　被我们用来求答案的矩阵长这样：

　　　　10^t     0      0

　　　　1         1      0

　　　　0         1      1

　　　其中t随我们现在处理的数的位数而改变。

　　然后这道题就硬生生的被我们搞成了一个矩阵快速幂的裸题。只要注意矩阵乘不满足交换律就是了。

　　

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<string>
#include<cmath>
using namespace std;
long long n,m;
struct no{
    long long x,y;
    long long a[20][20];
    no operator *(const no &c){
        no b;
        memset(b.a,0,sizeof(b.a));
        b.x=x;
        b.y=y;
        for(int i=1;i<=x;i++)
        {
            for(int j=1;j<=y;j++)
            {
                for(int k=1;k<=y;k++)
                {
                    b.a[i][j]+=((a[i][k]%m)*(c.a[k][j]%m))%m;
                    b.a[i][j]%=m;
                }
            }
        }
        return b;
    }
};
no ksm(long long x,no a,no b){
    no ans=a;
    while(x)
    {
        if((x&1)) ans=ans*b;
        b=b*b;
        x>>=1;
    }
    return ans;
}
long long get(long long x){
    long long now=1;
    no ans,a;
    memset(a.a,0,sizeof(a.a));
    a.x=a.y=3;
    a.a[2][1]=a.a[2][2]=a.a[3][2]=a.a[3][3]=1;
    memset(ans.a,0,sizeof(ans.a));
    ans.x=1,ans.y=3;
    ans.a[1][1]=0;
    ans.a[1][2]=ans.a[1][3]=1;
    for(int i=1;;i++)
    {
        now*=10;
        if(x>(now-1))
        {
            a.a[1][1]=now;
            ans=ksm(now-now/10,ans,a);
        }
        else
        {
            a.a[1][1]=now;
            ans=ksm(x-(now/10-1),ans,a);
            break;
        }
    }
    return ans.a[1][1];
}
int main(){
    scanf("%lld%lld",&n,&m);
    printf("%lld
",get(n));
    //while(1);
    return 0;
}