题解 P3216 【[HNOI2011]数学作业】

muller · 2019-02-06 11:18:47 · 题解

40 pts

首先我们有fn=fn-1*10^k+i;

这样我们打个暴力得手

100 pts

我们考虑优化，即发现其实k的变化最多18以内

所以我们考虑对于不同的k分段考虑

对于每个k既可以得到一个矩阵

我们考虑如何建立这个矩阵

于是我们思考这个矩阵是

[ f[i] i + 1 1] 乘 一个3乘3的矩阵

得到[ f[i + 1] i + 2 1]

我们可以推出矩阵为

[ 10 ^ k 0 0]

[ 1 1 0]

[0 1 1]

所以分段考虑矩阵乘法

同时建立一个初始矩阵即可

放上我的代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct mat {
    ll a[3][3];
} c, ans;
ll n, m, tmp, t[20];
mat operator *(mat a, mat b) {
    mat c;
    int i, j, k;
    for (i = 0; i < 3; ++i)
        for (j = 0; j < 3; ++j) c.a[i][j] = 0;
    for (i = 0; i < 3; ++i)
        for (j = 0; j < 3; ++j)
            for (k = 0; k < 3; ++k) c.a[i][j] = (c.a[i][j] + a.a[i][k] * b.a[k][j]) % m;
    return c; 
}
mat pw(mat x, ll y) {
    if (y == 1) return x;
    mat z = pw(x, y / 2);
    z = z * z;
    if (y & 1) z = z * x;
    return z;
}
int main() {
    int i;
    scanf("%lld%lld", &n, &m);
    ans.a[0][1] = ans.a[0][2] = c.a[1][0] = c.a[1][1] = c.a[2][1] = c.a[2][2] = 1;
    for (t[0] = i = 1; i <= 18; ++i) t[i] = t[i - 1] * 10;
    for (i = 1;; ++i) {
        c.a[0][0] = t[i] % m;
        tmp = min(n, t[i] - 1) - t[i - 1] + 1;
        ans = ans * pw(c, tmp);
        if (t[i] - 1 >= n) break;
    }
    printf("%lld\n", ans.a[0][0]);
    return 0;
}