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

时间：2021-11-23 20:57:14

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位，那么我们就对每一位分情况进行矩阵乘法，如19时，T[0][0]为10，1099时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;

}

相关文章