codevs 2314 数学作业

2314 数学作业

2011年省队选拔赛湖南

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 大师 Master

题目描述 Description

小 C 数学成绩优异，于是老师给小 C 留了一道非常难的数学作业题：给定正整数 N 和 M ，要求计算 Concatenate (1 .. N ) Mod M 的值，其中Concatenate (1 .. N ) 是将所有正整数 1, 2, …, N 顺序连接起来得到的数。例如， N = 13, Concatenate (1 .. N ) = 12345678910111213. 小 C 想了大半天终于意识到这是一道不可能手算出来的题目，于是他只好向你求助，希望你能编写一个程序帮他解决这个问题。

输入描述 Input Description

只有一行为用空格隔开的两个正整数 N 和 M

输出描述 Output Description

仅包含一个非负整数，表示 Concatenate (1 .. N ) Mod M 的值

样例输入 Sample Input

13 13

样例输出 Sample Output

数据范围及提示 Data Size & Hint

其中 30%的数据满足1≤ N ≤1000000；100%的数据满足1≤ N ≤1018且1≤ M ≤109

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef int matrix[][];

typedef long long ll;

ll N;

int MOD;

matrix mat,Q,tmp;

void Init_matrix(){

    memset(mat,,sizeof(mat));

    mat[][]=mat[][]=mat[][]=mat[][]=mat[][]=;

    memset(Q,,sizeof(Q));

    for(int i=;i<;i++)Q[i][i]=;

}

void Mul(matrix &a,matrix &b){

    memset(tmp,,sizeof(tmp));

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

        for(int k=;k<;k++)

            for(int j=;j<;j++)

                if((tmp[i][j]+=ll(a[i][k])*b[k][j]%MOD)>=MOD)

                    tmp[i][j]-=MOD;

    memcpy(a,tmp,sizeof(a));

}

void Power(matrix &a,matrix &b,ll k){

    while(k){if(k&)Mul(a,b);k>>=;Mul(b,b);}

}

int main(){

    scanf("%lld%d",&N,&MOD);

    int len=,B=,C=;

    ll p=;

    for(ll t=N;t;t/=,len++);

    for(int i=;i<len;i++){

        Init_matrix();

        mat[][]=(p=p*)%MOD;

        Power(Q,mat,p-p/);

        B=(ll(B)*Q[][]%MOD+ll(C)*Q[][]%MOD+Q[][])%MOD;

        C=((p%MOD)-+MOD)%MOD;

    }

    Init_matrix();

    mat[][]=p*%MOD;

    Power(Q,mat,N-p+);

    B=(ll(B)*Q[][]%MOD+ll(C)*Q[][]%MOD+Q[][])%MOD;

    printf("%d\n",B);

    return ;

}

巴特西

codevs 2314 数学作业

2314 数学作业

最新文章

热门文章