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

· · 题解

/* * P:3216

* Au:Small_Ash

* 嗯，一开始看题的时候就觉得肯定是O（N）的奇怪算法（毕竟是一直连接一个数啊，肯定要连接一次取模一次）

* 然后数据范围给了我一巴掌！10^18 Are you sure? 嗯，那就是O(logN)没跑了

* 等等啊，我们看看第N个数的计算方法啊，就是前一个数接数嘛。。

* 等等，接数，等等 ，前一个？ N-1=>N 。。。

* 我好想发现了什么，递推？？ f[N]=f[N-1]*10^k+N;（k是N的位数）

* 等等，f[N]哪门子开的出来啊。。。

* 等等，递推，logN。。。

* 。。。

* 哦，矩阵快速幂！

* 然后就有了思路。。。

* {10^k,0,0}

* {F[n],n,1}= { 1, 1,0} * {F[n-1],n-1,1} (f[N]=f[N-1]*10^k+N可变形为f[N]=f[N-1]*10^k+(N-1)+1)

* { 1, 1,1}

* * OK！然后就是实现了。。。

* 三点提醒

* 1.全部用long long，不要吝啬内存。

* 2.凡是有 long long*long long 的计算全部改成 ((long long)%p*(long long)%p)%p

* (别问我为什么会知道，我会说我之前所有带取模的递推都是死在取模不够彻底上吗。。。)

* 3.10^k的计算要分段，这段的实现可能会让你抓狂，忍住慢慢改，这里给一组大数据供各位调试。

* Input : 948177742992423376 819143553 Output : 578278753

* 以上，下面是代码。

*/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
long long n,p;
struct zj{
    long long a[5][5];
    zj operator = (int k){
        a[1][1]=1;
        for (int i=1;i<=k;i++)
        a[1][1]*=10;
        a[1][1]%=p;
        a[1][2]=0;
        a[1][3]=0;
        a[2][1]=1;
        a[2][2]=1;
        a[2][3]=0;
        a[3][1]=1;
        a[3][2]=1;
        a[3][3]=1;
        return *this;
    }
    zj operator * (zj b){
        zj c;
           for (int i=1;i<=3;i++)
             for (int j=1;j<=3;j++){
                 c.a[i][j]=0;
                 for (int k=1;k<=3;k++){
                    c.a[i][j]+=(a[i][k])%p*(b.a[k][j])%p;  
                    c.a[i][j]%=p;
                }
            }
        return c;
    }
    zj operator ^ (long long x){
        zj c,a;a=*this;
           for(int i=1;i<=3;i++)
            for(int j=1;j<=3;j++)
                c.a[i][j]=(i==j); 
        for(;x;x>>=1){
            if(x&1) c=c*a;
               a=a*a;
        }
        return c;
    }
}A[20],B;
long long pow10(int x){
    long long out=1;
    for (int i=1;i<=x;i++) out*=10;
    return out;
}
int main(){
    scanf("%lld%lld",&n,&p);
    int k=0;long long nn=n;
    while (nn) {k++;nn/=10;}
    for (int i=1;i<k;i++){
        A[i]=i;
        A[i]=A[i]^(pow10(i-1)*9);
    }
    nn=n-pow10(k-1)+1;
    A[k]=k;
    A[k]=A[k]^nn;
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            B.a[i][j]=(i==j);
    for (int i=1;i<=k;i++) B=B*A[i];
    printf("%lld",B.a[3][1]);
    return 0;
}