首页 > 代码库 > LJX的校园:入学典礼(C++)

LJX的校园:入学典礼(C++)

LJX的校园:入学典礼
难度级别:C; 运行时间限制:45ms; 运行空间限制:256000KB; 代码长度限制:2000000B
试题描述

     LJX上小学啦!他与YSM,YSF,WHT,LTJ等人都是校友。今天,是他人生中“溺亡”的一天。今天,他要向同学们证明他的数学很“乐呵”。于是,刚学会简单的A+B问题的他,在课上,向冤家对头 斯沃琪 挑战 QAQ,斯沃琪 队有YZM,SJY,ZZQ等人。而LJX队有他的好朋(ji)友:YSM,YSF,WHT,LTJ,LZH等人,实力不弱小觑。有这么一道题:

      给定正整数N,M,要求计算1,2,……,N连接起来(1234567891011……N)mod M的值。

    “新兵”LJX想了想,要是M是3,或者9,他一定会。但是M什么都可以,只要小于INF。“预约”了各种方法以后,费劲脑筋想不出来。于是,右转向了(呵呵)他的(ZHU)队友们。可他们已经跑了 TAT。jue ruo LJX找到了你,他跪求你编一个程序帮他解决问题。否则,他将在毕业典礼上“锻炼”,并且被可怕的斯沃琪虐残 QAQ

输入
* 一行:正整数N,M。
输出
* 一行:按要求输出
输入示例
输入样例1
13 13
输入样例2
12345678910 1000000000
输出示例
输出样例1
4
输出样例2
345678910
其他说明
N<=10^18
M<=10^9
这数据是在坑LJX呀

用今天学的矩阵快速幂
哦,不,是分段矩阵快速幂

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

#define MAXN 4

using namespace std;

typedef long long int LL;

int mod;

struct matrix
{
LL p[MAXN][MAXN];
}ans,tmp;

matrix operator*(matrix a,matrix b)
{
matrix c;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
{
c.p[i][j]=0;
for(int k=1;k<=3;k++)
c.p[i][j]=(c.p[i][j]+((a.p[i][k]%mod)*(b.p[k][j]%mod))%mod)%mod;
}
return c;
}

void cal(LL t,LL last)
{
memset(tmp.p,0,sizeof(tmp.p));
tmp.p[1][1]=t;
tmp.p[2][1]=tmp.p[3][1]=tmp.p[2][2]=tmp.p[3][2]=tmp.p[3][3]=1;
LL y=last-t/10+1;
while(y)
{
if(y&1) ans=ans*tmp;
tmp=tmp*tmp;
y>>=1;
}
}

int main()
{
for(int i=1;i<=3;i++)
ans.p[i][i]=1;
LL n;
scanf("%lld%lld",&n,&mod);
LL t=10;
while(n>=t)
{
cal(t,t-1);
t*=10;
}
cal(t,n);
printf("%lld\n",ans.p[3][1]);
return 0;
}

LJX的校园:入学典礼(C++)