小 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≤1018且1≤M≤109.
输出格式：
输出文件 output.txt 仅包含一个非负整数，表示 Concatenate (1 .. N) Mod M 的值。
13 13
4
矩阵快速幂：
si+1=si*10x+i+1
当前状态S=(si i 1)
递推矩阵T=
10x 0 0
1 1 0
1 1 1
注意所有变量开long long
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 long long Mod; 7 struct Matrix 8 { 9 long long a[4][4]; 10 Matrix operator * (const Matrix &x) const{ 11 Matrix ans; 12 memset(ans.a,0,sizeof(ans.a)); 13 for(int i=0;i<=2;++i) 14 for(int j=0;j<=2;++j) 15 for(int k=0;k<=2;++k) 16 ans.a[i][j]=(ans.a[i][j]+(a[i][k]*x.a[k][j])%Mod)%Mod; 17 return ans; 18 } 19 }; 20 Matrix k; 21 Matrix s; 22 long long last; 23 Matrix pow(Matrix x,long long p) 24 { 25 Matrix res; 26 res.a[0][0]=last;res.a[0][1]=0;res.a[0][2]=0; 27 res.a[1][0]=1;res.a[1][1]=1;res.a[1][2]=0; 28 res.a[2][0]=1;res.a[2][1]=1;res.a[2][2]=1; 29 while (p) 30 { 31 if (p%2==1) 32 { 33 res=res*k; 34 } 35 k=k*k; 36 p/=2; 37 } 38 return res; 39 } 40 long long min(long long a,long long b) 41 { 42 if (a<b) return a; 43 else return b; 44 } 45 int main() 46 { 47 long long n,i; 48 cin>>n>>Mod; 49 s.a[0][0]=0;s.a[0][1]=0;s.a[0][2]=1; 50 i=1; 51 do 52 { 53 i*=10; 54 last=i%Mod; 55 k.a[0][0]=i%Mod;k.a[0][1]=0;k.a[0][2]=0; 56 k.a[1][0]=1;k.a[1][1]=1;k.a[1][2]=0; 57 k.a[2][0]=1;k.a[2][1]=1;k.a[2][2]=1; 58 long long l=min(i-1,n)-i/10; 59 } 60 while (n>=i); 61 cout<<s.a[0][0]; 62 }
原文：http://www.cnblogs.com/Y-E-T-I/p/7138041.html