BZOJ2326【HNOI2011】数学作业 <矩阵快速幂优化DP>

Problem

【HNOI2011】数学作业

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

$\mathrm{小C}$数学成绩优异，于是老师给$\mathrm{小C}$留了一道非常难的数学作业题：
给定正整数$N$和$M$，要求计算$Concatenate(1\cdots N)\mod{M}$的值，其中$Concatenate(1\cdots N)$是将所有正整数$1,2,\cdots,N$顺序连接起来得到的数。
例如$N=13$，$Concatenate(1\cdots N)=12345678910111213$。
$\mathrm{小C}$想了大半天终于意识到这是一道不可能手算出来的题目，于是他只好向你求助，希望你能编写一个程序帮他解决这个问题。

Input

只有一行且为用空格隔开的两个正整数$N$和$M$。

Output

仅包含一个非负整数，表示$Concatenate(1\cdots N)\mod{M}$的值。

Sample Input

13 13

Sample Output

4

HINT

$1\le N\le10^{18}$且$1\le M\le10^9$。

标签：DP 矩阵快速幂

Solution

显然是矩阵快速幂优化$\mathrm{DP}$。

设$1\sim i$顺次连接后模$M$的值为$f_i$，所求为$f_N$。
构建矩阵。由于每次都是将$f_{i-1}$乘$10^{\lfloor\lg{i}\rfloor}$后加上$i$，需要三个参数，即$f_{i-1}$,$10^{\lfloor\lg{i}\rfloor}$,$i$。构造$3\times3$的转移矩阵：

$$\begin {pmatrix} f_{i-1}&i-1&1 \end {pmatrix} \times \begin {pmatrix} 10^{\lg{i}}&0&0\\ 1&1&0\\ 1&1&1\\ \end {pmatrix} = \begin {pmatrix} f_i&i&1 \end {pmatrix}$$

分成若干$[10^k,10^{k+1})$的区间做矩阵快速幂后乘起来即可。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
lnt n, m, f;
struct Matrix {
    lnt ele[3][3];
    Matrix () {memset(ele, 0, sizeof ele);}
    inline Matrix operator * (const Matrix &x) const {
        Matrix ret;
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) for (int k = 0; k < 3; k++)
            ret.ele[i][j] = (ret.ele[i][j]+ele[i][k]*x.ele[k][j]%m)%m;
        return ret;
    }
};
Matrix Power(Matrix a, lnt k) {
    Matrix ret;
    for (int i = 0; i < 3; i++)
        ret.ele[i][i] = 1;
    for (; k; k >>= 1, a = a*a)
        if (k&1) ret = ret*a;
    return ret;
}
int main() {
    read(n), read(m);
    for (lnt i = 1; i <= n; i *= 10) {
        Matrix a, b;
        a.ele[0][0] = f, a.ele[0][1] = (i-1)%m, a.ele[0][2] = 1;
        b.ele[0][0] = i*10%m, b.ele[0][1] = 0, b.ele[0][2] = 0;
        b.ele[1][0] = 1, b.ele[1][1] = 1, b.ele[1][2] = 0;
        b.ele[2][0] = 1, b.ele[2][1] = 1, b.ele[2][2] = 1;
        a = a*Power(b, min(n, i*10-1)-i+1), f = a.ele[0][0];
    }
    return printf("%lld\n", f), 0;
}