洛谷题单指南-基础线性代数-P3216 [HNOI2011] 数学作业

原题链接：https://www.luogu.com.cn/problem/P3216

题意解读：求数列的第n个

解题思路：根据题意，要求的是Concatenate(n)简化成C(n) = C(n-1) * (log₁₀n+1) + n

由于lgn+1不固定，但是在1-9,10-99,100~999...这些区间内是固定的，最多18个区间

因此，可以根据n值来分区间计算

比如：n = 1234

设A_i表示lgn+1为i的情况

D(9) = D(1) * A₁⁸

D(99) = D(9) * A₂⁹⁰

D(999) = D(99) * A₃⁹⁰⁰

D(1234) = D(999) * A₄²³⁵

注意：编程中如果使用log10()来计算整数长度，会存在精度问题，替换为以下代码即可：

LL len(LL x)
{LL l = 0;while(x > 0) {x /= 10;l++;}return l;
}

100分代码：

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
LL n, m, pow10[19];
struct Matrix
{LL a[5][5];Matrix(){memset(a, 0, sizeof(a));}Matrix operator * (const Matrix &to) const{Matrix res;for(int i = 1; i <= 3; i++)for(int j = 1; j <= 3; j++)for(int k = 1; k <= 3; k++)res.a[i][j] = (res.a[i][j] + a[i][k] * to.a[k][j] % m) % m;return res;}
};Matrix ksm(Matrix &a, LL b)
{Matrix res;res.a[1][1] = res.a[2][2] = res.a[3][3] = 1;while(b){if(b & 1) res = res * a;b >>= 1;a = a * a;  }return res;
}LL len(LL x)
{LL l = 0;while(x > 0) {x /= 10;l++;}return l;
}Matrix newA()
{Matrix A;A.a[1][1] = pow10[1], A.a[1][2] = 0, A.a[1][3] = 0;A.a[2][1] = 1, A.a[2][2] = 1, A.a[2][3] = 0;A.a[3][1] = 1, A.a[3][2] = 1, A.a[3][3] = 1;return A;
}int main()
{cin >> n >> m;pow10[0] = 1;for(int i = 1; i <= 18; i++) pow10[i] = pow10[i - 1] * 10 % m;Matrix d;d.a[1][1] = 1, d.a[1][2] = 1, d.a[1][3] = 1;if(n <= 9){Matrix A = newA();d = d * ksm(A, n - 1);}else {LL l = 1, r = 9;while(true){Matrix A = newA();A.a[1][1] = pow10[len(r)] % m;d = d * ksm(A, r - l);if(len(r) + 1 == len(n)) break;l = r, r = r * 10 + 9;}Matrix A = newA();A.a[1][1] = pow10[len(n)] % m;d = d * ksm(A, n - r);}cout << d.a[1][1];return 0;
}