【bzoj2326】[HNOI2011]数学作业

2015.04.14 15:57 Tue | 2次阅读 | 旧日oi | 固定链接 | 源码

Description

.jpg).jpg)

题解

递推是一眼就可以看出来的,问题在于如何优化。
对于10^k~10^(k+1)-1这之间的数,前数每次都是乘10^k,这就让我们想到了矩阵,建立3*3的矩阵
f[n-1]      n      1           10^k      0        0          f[n]    n+1       1

  •          1          1        0    = 0          1         1 分段转移即可,时间复杂度就是对每段取个log,最大不会超过是log10^180左右吧,常数27。。不知道对不对,反正很快就是了…… ##我的程序
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
    long long matrix[3][3];
}mul;
long long n,m;
long long qpow(long long a,long long b)
{
    long long ans=1;
    while(b)
    {
        if(b&1) ans*=a;
        a*=a;
        b>>=1;
    }
    return ans;
}
node matrix_mul(node &a,node &b)
{
    node temp;
    memset(&temp,0,sizeof(temp));
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            for(int k=0;k<3;k++)
            temp.matrix[i][j]=(temp.matrix[i][j]+(a.matrix[i][k]*b.matrix[k][j])%m)%m;
        }
    }
    return temp;
}
long long matrix_pow(long long a,long long t,int k)
{
    mul.matrix[0][0]=qpow(10,k)%m;
    node ans,temp;
    memset(&ans,0,sizeof(ans));memset(&temp,0,sizeof(temp));
    ans.matrix[0][0]=a%m;
    ans.matrix[0][1]=qpow(10,k-1)%m;
    ans.matrix[0][2]=1;
    temp.matrix[0][0]=temp.matrix[1][1]=temp.matrix[2][2]=1;
    while(t)
    {
        if(t&1) temp=matrix_mul(temp,mul);
        mul=matrix_mul(mul,mul);
        t>>=1;
    }
    ans=matrix_mul(ans,temp);
    return ans.matrix[0][0];
}
int main()
{
    cin>>n>>m;
    int len=0;
    long long temp=0;
    long long nn=n;
    while(nn)
    {
        mul.matrix[0][1]=mul.matrix[0][2]=mul.matrix[1][2]=mul.matrix[2][0]=0;
        mul.matrix[1][0]=mul.matrix[1][1]=mul.matrix[2][1]=mul.matrix[2][2]=1;
        len++;
        if(nn>=10) temp=matrix_pow(temp,qpow(10,len)-qpow(10,len-1),len);
        else
        temp=matrix_pow(temp,n-qpow(10,len-1)+1,len);
        nn/=10;
    }
    cout<<temp<<endl;
}```