首页 > 代码库 > 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。“预约”了各种方法以后,费劲脑筋想不出来。于是,右转向了(呵呵)他的( |
输入
|
* 一行:正整数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++)