首页 > 代码库 > 首师大附中科创教育平台 我的刷题记录 3120 LJX的校园:入学典礼

首师大附中科创教育平台 我的刷题记录 3120 LJX的校园:入学典礼

今天给大家献上“D”级题:LJX的校园:入学典礼!!

  试题编号:3120 
LJX的校园:入学典礼
难度级别:D; 运行时间限制: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呀

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

好的,以上就是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的校园:入学典礼!!!!!

 

首师大附中科创教育平台 我的刷题记录 3120 LJX的校园:入学典礼