[HNOI2011]数学作业

BZOJ2326...
 
这道题告诉我们快速幂没写对也是会导致WA的...
 
矩阵乘法模板题,
设A(x) =
(
10^x   1      0 
0         1      1
0         0      1
)

(这什么鬼格式啊...哎呀不要在意细节(-ω-))

设B = (0 1 1)^T
 
于是可得:
答案为R = ((A(1)^9 + A(2)^(99-9) + ... + A(k)^(n-(10^k-1 - 1)) * B)这个矩阵的第一行第一列,快速幂即可
 
代码如下:

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <iostream>

  

typedef unsigned long long Long;

  

Long n = 0;

Long m = 0;

 

Long mul(Long a,Long b)

{

    Long r = 0;

    Long M = (((Long)1LL) << 63);

    while(M)

    {

        r = (r + r) % m;

        if(b & M)

            r = (r + a) % m;

        M >>= 1;

    }

    return r;

}

 

Long pow(Long a,Long b)

{

    Long r = 1LL;

    Long M = (((Long)1LL) << 63);

    while(M)

    {

        r = mul(r,r);

        if(b & M)

            r = mul(r,a);

        M >>= 1;

    }

    return r;

}

      

struct mat

{

    Long a[5][5];

    int r;

    int c;

    mat()

    {

        clear();

    }

    void clear()

    {

        memset(a,0,sizeof(a));

        r = 0;

        c = 0;

    }

    void init_e()

    {

        clear();

        r = 3;

        c = 3;

        for(int i = 1;i <= 3;i++)

            a[i][i] = 1LL;

    }

      

    void init_l(int k = 1)

    {

        clear();

        r = 3;

        c = 3;

        a[1][1] = pow((Long)10,(Long)k);

        a[1][2] = 1;

        a[2][2] = 1;

        a[2][3] = 1;

        a[3][3] = 1;

    }

      

    void init_r()

    {

        clear();

        r = 3;

        c = 1;

        a[2][1] = 1;

        a[3][1] = 1;

    }

      

    mat operator * (const mat & B)const

    {

        mat C;

        const mat & A = (*this);

        C.r = A.r;

        C.c = B.c;

        for(int r = 1;r <= A.r;r++)

        {

            for(int c = 1;c <= B.c;c++)

            {

                for(int i = 1;i <= A.c;i++)

                {

                    C.a[r][c] += mul(A.a[r][i],B.a[i][c]);

                    C.a[r][c] %= m;

                }

            }

        }

          

        return C;

    }

  

    mat operator ^ (Long b)const

    {

        const mat & A = (*this);

        mat R;

        R.init_e();

        Long M = (((Long)1LL) << 63);

        while(M)

        {

            R = R * R;

            if(b & M)

                R = A * R;

            M >>= 1;

        }

        return R;

    }

};

  

mat A;

mat B;

mat R;

  

int main()

{

     

    std::cin>>n>>m;

     

     

    R.init_e();

    B.init_r();

     

    Long k = 1LL;

    Long last_k = 0LL; 

    int Q = 0; 

    while(n)

    {

        Q++; 

        k *= 10LL;

        Long K = k - 1;

        A.init_l(Q);

        if(n >= K)

        {

            R = (A ^ (K - last_k)) * R;

        }

        else

        {

            R = (A ^ (n - last_k)) * R;

            break;

        }

        last_k = K;

    }

     

    R = R * B;

      

    std::cout<<R.a[1][1]<<std::endl;

      

    return 0;

}