[HNOI2011]数学作业

YYY posted @ 2015年7月13日 22:07 with tags 矩阵乘法 快速幂 , 132 阅读
 
这道题告诉我们快速幂没写对也是会导致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;
}
 
 
LOL

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter