数学作业

题目描述

小 C 数学成绩优异，于是老师给小 C 留了一道非常难的数学作业题：

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

输入输出格式

输入格式：

 

从文件input.txt中读入数据，输入文件只有一行且为用空格隔开的两个正整数N和M，其中30%的数据满足 1≤N≤1000000 ；100%的数据满足 1≤N≤10^18 且 1≤M≤10^9 .

 

输出格式：

 

输出文件 output.txt 仅包含一个非负整数，表示 Concatenate (1 .. N) Mod M 的值。

 

输入输出样例

输入样例#1： 

13 13

输出样例#1： 

　4

 

---

　　分析：明显矩阵加速。代码打出来确实也就是个模板，但是中间矩阵的构造确实非(sang)常(xin)的(bing)难(kuang)。

　　首先分析，对于一个k位数x，很明显得到的结果应该是f(x)=f(x-1)*10^k+x;

　　那么经过一番简（yao）短（ming）的思考后，可以得到中间矩阵应该是

10^k	0	0
1	1	0
0	1	1

 

 　　而初始矩阵应为:

0	1	1
0	0	0
0	0	0

 

　　那么剩下的就是矩阵加速模板了~

　　Code：

 

#include
       
        using namespace std;typedef long long ll;ll n,mod;struct Matrix{    ll a[5][5];    Matrix(){memset(a,0,sizeof(a));}    Matrix(ll b[5][5]){memcpy(a,b,sizeof(a));}    friend Matrix operator * (const Matrix a,const Matrix b){        Matrix ret;        for(int i=0;i<=2;i++)        for(int j=0;j<=2;j++)        for(int k=0;k<=2;k++)        ret.a[i][j]=(ret.a[i][j]+(a.a[i][k]*b.a[k][j])%mod)%mod;        return ret;    }}K,T;int main(){    cin>>n>>mod;ll now=0;    K.a[0][0]=0;K.a[0][1]=1;K.a[0][2]=1;    for(ll i=10;now
        
         >=1;}        now=min(i-1,n);}    cout<