CJOJ 1331 【HNOI2011】数学作业 / Luogu 3216 【HNOI2011】数学作业 / HYSBZ 2326 数学作业（递推，矩阵）

Description

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

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

Input

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

Output

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

Sample Input

13 13

Sample Output

4

Http

CJOJ:http://oj.changjun.com.cn/problem/detail/pid/1331 Luogu:https://www.luogu.org/problem/show?pid=3216 HYSBZ:https://vjudge.net/problem/HYSBZ-2326

Source

递推，矩阵

解决思路

根据题意，我们可以设出递推式f[i]=f[i-1]*Num[i]+i,其中Num[i]是i的位数。因为题目中数据范围很大，所以我们很自然地就想到了矩阵优化（如果读者您还不知道什么是矩阵、矩阵优化或是矩阵快速幂，可以到我的这一篇文章中阅读）

我们可以列出的矩阵递推式是：\[F_i=F_{i-1}*T=\begin{bmatrix} f_{i-1}&i&1\\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}* \begin{bmatrix} Num[i] & 0 & 0\\1 & 1&0 \\ 0& 1&1 \end{bmatrix} = \begin{bmatrix} f_i=f_{i-1}*Num[i] & i+1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}\] 但是这样有一个问题，这个递推矩阵T中有一个数是变量，这不符合我们要实现矩阵快速幂的要求，若直接相乘，就失去了我们用矩阵优化的意义。

于是我们再次观察题目，题目中表示了数字不会超过18位，那么我们就对每一位分情况进行矩阵乘法，如1~9时，T[0][0]为10，10~99时T[0][0]为100,100~999时T[0][0]为1000，依次类推，分别进行快速幂计算，这样就能达到优化的目的了。

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long ll n,m; class Matrix//定义矩阵 { public: ll M[3][3]; Matrix() { memset(M,0,sizeof(M)); } Matrix(ll Arr[3][3]) { for (int i=0;i<3;i++) for (int j=0;j<3;j++) M[i][j]=Arr[i][j]; } }; Matrix operator * (Matrix A,Matrix B)//重载乘法操作 { Matrix Ans; for (int i=0;i<3;i++) for (int j=0;j<3;j++) for (int k=0;k<3;k++) Ans.M[i][j]=(Ans.M[i][j]+A.M[i][k]*B.M[k][j]%m)%m; return Ans; } int main() { cin>>n>>m; ll now; ll last=0; ll a[3][3]={{0,1,1},{0,0,0},{0,0,0}}; ll b[3][3]={{0,0,0},{1,1,0},{0,1,1}}; Matrix A(a); for (ll i=10;last<n;i=i*10)//分情况进行矩阵快速幂 { b[0][0]=i%m; Matrix B(b); now=min(i-1,n)-last;//now是当前这么多位能到的最大数，如两位时是99-9=9,三位时是999-99=900,注意要与n取一次最小 //cout<<now<<' '<<last<<endl; //system("pause"); while (now!=0)//矩阵快速幂 { //cout<<now<<endl; if (now&1) A=A*B; B=B*B; now=now>>1; } last=min(i-1,n);//Last记录上次能到的最大数 } cout<<A.M[0][0]<<endl; return 0; }

转载于:https://www.cnblogs.com/SYCstudio/p/7182656.html

相关资源：JAVA上百实例源码以及开源项目