题目描述
小 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 的值。
输入输出样例
输入样例#1：
13 13
输出样例#1：
4
矩阵快速幂：
si+1=si*10x+i+1
当前状态S=(si i 1)
递推矩阵T=
10x 0 0
1 1 0
1 1 1
注意所有变量开long long
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long Mod;
struct Matrix
{
long long a[][];
Matrix operator * (const Matrix &x) const{
Matrix ans;
memset(ans.a,,sizeof(ans.a));
for(int i=;i<=;++i)
for(int j=;j<=;++j)
for(int k=;k<=;++k)
ans.a[i][j]=(ans.a[i][j]+(a[i][k]*x.a[k][j])%Mod)%Mod;
return ans;
}
};
Matrix k;
Matrix s;
long long last;
Matrix pow(Matrix x,long long p)
{
Matrix res;
res.a[][]=last;res.a[][]=;res.a[][]=;
res.a[][]=;res.a[][]=;res.a[][]=;
res.a[][]=;res.a[][]=;res.a[][]=;
while (p)
{
if (p%==)
{
res=res*k;
}
k=k*k;
p/=;
}
return res;
}
long long min(long long a,long long b)
{
if (a<b) return a;
else return b;
}
int main()
{
long long n,i;
cin>>n>>Mod;
s.a[][]=;s.a[][]=;s.a[][]=;
i=;
do
{
i*=;
last=i%Mod;
k.a[][]=i%Mod;k.a[][]=;k.a[][]=;
k.a[][]=;k.a[][]=;k.a[][]=;
k.a[][]=;k.a[][]=;k.a[][]=;
long long l=min(i-,n)-i/;
}
while (n>=i);
cout<<s.a[][];
}