题解：P3216 [HNOI2011] 数学作业

题目

给定正整数 ，要求计算 的值，其中 是将 所有正整数 顺序连接起来得到的数。

例如，，。

对于 的数据，，。

题解

首先抛开数据范围，考虑递推转移，写出式子：

比较显然的是矩阵加速递推，但是向量是什么？这就要看我们需要什么。

注意到是二维一阶，但是需要同时维护 以及 ，所以还需要带有一个常数 ，写出我们的向量 就是：

从而我们的矩阵 就很好写出来了：

注意到我们需要根据 进行分组，也就是 ，分组就有两个问题：

1. 组与组之间的衔接问题，因为更新 之后，我们同时更新矩阵 ，这样我们可以继续使用上次中断的 无缝衔接了；
2. 注意边界，我们正常的幂次就是为 ，但是要和 取 。

代码如下：

#include<bits/stdc++.h>
#define LL unsigned long long

using namespace std;

LL n, mod;

struct Matrix {
    int lenRow;
    int lenCol;
    vector< vector<LL> > M;
    inline void resize(int row, int col) {
        lenRow = row;
        lenCol = col;
        M.resize(row, vector<LL>(col, 0));
        return;
    }
    Matrix operator * (const Matrix& another) const {
        Matrix res;
        res.resize(lenRow, another.lenCol);
        for (int i = 0; i < res.lenRow; ++i)
            for (int j = 0; j < res.lenCol; ++j)
                for (int k = 0; k < another.lenRow; ++k)
                    res.M[i][j] = (res.M[i][j] + M[i][k] * another.M[k][j]) % mod;
        return res;
    }
};

inline Matrix Pow(Matrix res, Matrix base, LL expo) {
    while (expo) {
        if (expo & 1)
            res = res * base;
        base = base * base;
        expo >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> mod;

    Matrix vec;
    vec.resize(1, 3);
    vec.M = {
        {0, 1, 1}
    };
    Matrix trans;
    trans.resize(3, 3);
    trans.M = {
        {0, 0, 0},
        {1, 1, 0},
        {0, 1, 1}
    };

    for (LL i = 1; i <= n; i = i * 10) {
        trans.M[0][0] = (i % mod * 10 % mod) % mod;
        vec = Pow(vec, trans, min(9 * i, n - i + 1));
    }

    cout << vec.M[0][0];
    return 0;
}