首页 > 代码库 > codevs 2314 数学作业

codevs 2314 数学作业

2024-09-30 22:24:02   203人阅读

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

4

数据范围及提示 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[3][3];typedef long long ll;ll N;int MOD;matrix mat,Q,tmp;void Init_matrix(){    memset(mat,0,sizeof(mat));    mat[0][1]=mat[0][2]=mat[1][1]=mat[1][2]=mat[2][2]=1;    memset(Q,0,sizeof(Q));    for(int i=0;i<3;i++)Q[i][i]=1;}void Mul(matrix &a,matrix &b){    memset(tmp,0,sizeof(tmp));    for(int i=0;i<3;i++)        for(int k=0;k<3;k++)            for(int j=0;j<3;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&1)Mul(a,b);k>>=1;Mul(b,b);}}int main(){    scanf("%lld%d",&N,&MOD);    int len=0,B=0,C=0;    ll p=1;    for(ll t=N;t;t/=10,len++);    for(int i=1;i<len;i++){        Init_matrix();        mat[0][0]=(p=p*10)%MOD;        Power(Q,mat,p-p/10);        B=(ll(B)*Q[0][0]%MOD+ll(C)*Q[0][1]%MOD+Q[0][2])%MOD;        C=((p%MOD)-1+MOD)%MOD;    }    Init_matrix();    mat[0][0]=p*10%MOD;    Power(Q,mat,N-p+1);    B=(ll(B)*Q[0][0]%MOD+ll(C)*Q[0][1]%MOD+Q[0][2])%MOD;    printf("%d\n",B);    return 0;}

 

codevs 2314 数学作业


联系
我们