题目
解析
矩阵快速幂模板题
构造矩阵
\[\begin{bmatrix}a_0&a_1&a_2&a_3&a_4&a_5&a_6&a_7&a_8&a_9\\
1&0&0&0&0&0&0&0&0&0\\
0&1&0&0&0&0&0&0&0&0\\
0&0&1&0&0&0&0&0&0&0\\
0&0&0&1&0&0&0&0&0&0\\
0&0&0&0&1&0&0&0&0&0\\
0&0&0&0&0&1&0&0&0&0\\
0&0&0&0&0&0&1&0&0&0\\
0&0&0&0&0&0&0&1&0&0\\
0&0&0&0&0&0&0&0&1&0\\
\end{bmatrix}^{n-9}
\begin{bmatrix}f_{n-1}\\f_{n-2}\\f_{n-3}\\f_{n-4}\\f_{n-5}\\f_{n-6}\\f_{n-7}\\f_{n-8}\\f_{n-9}\\f_{n-10}
\end{bmatrix}=\begin{bmatrix}f{n}\\f_{n-1}\\f_{n-2}\\f_{n-3}\\f_{n-4}\\f_{n-5}\\f_{n-6}\\f_{n-7}\\f_{n-8}\\f_{n-9}
\end{bmatrix}\]
1&0&0&0&0&0&0&0&0&0\\
0&1&0&0&0&0&0&0&0&0\\
0&0&1&0&0&0&0&0&0&0\\
0&0&0&1&0&0&0&0&0&0\\
0&0&0&0&1&0&0&0&0&0\\
0&0&0&0&0&1&0&0&0&0\\
0&0&0&0&0&0&1&0&0&0\\
0&0&0&0&0&0&0&1&0&0\\
0&0&0&0&0&0&0&0&1&0\\
\end{bmatrix}^{n-9}
\begin{bmatrix}f_{n-1}\\f_{n-2}\\f_{n-3}\\f_{n-4}\\f_{n-5}\\f_{n-6}\\f_{n-7}\\f_{n-8}\\f_{n-9}\\f_{n-10}
\end{bmatrix}=\begin{bmatrix}f{n}\\f_{n-1}\\f_{n-2}\\f_{n-3}\\f_{n-4}\\f_{n-5}\\f_{n-6}\\f_{n-7}\\f_{n-8}\\f_{n-9}
\end{bmatrix}\]
然后套矩阵快速幂就完了。
代码
因为我的快速幂是直接用构造好的矩阵，不用再构造一个单位矩阵，所以幂的次数少1
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 110;
int n, m;
class matrix {
public :
int a[N][N];
matrix() {
memset(a, 0, sizeof(a));
}
matrix operator * (const matrix &oth) const {
matrix ret;
memset(ret.a, 0, sizeof(ret.a));
for (int i = 1; i <= 10; ++i)
for (int j = 1; j <= 10; ++j)
for (int k = 1; k <= 10; ++k)
ret.a[i][j] = (ret.a[i][j] % m + (this->a[i][k] * oth.a[k][j]) % m) % m;
return ret;
}
} init;
template<class T>inline void read(T &x) {
x = 0; int f = 0; char ch = getchar();
while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
x = f ? -x : x;
return;
}
matrix qpow(matrix a, int b) {
matrix ans = init;
while (b) {
if (b & 1) ans = ans * a;
b >>= 1, a = a * a;
}
return ans;
}
int f[N][N], ans;
signed main() {
while (scanf("%lld%lld", &n, &m) != EOF) {
ans = 0;
memset(init.a, 0, sizeof(init.a));
for (int i = 1; i <= 10; ++i) read(init.a[1][i]);
if (n <= 9) {
printf("%lld\n", n);
continue;
}
for (int i = 2; i <= 10; ++i) init.a[i][i - 1] = 1;
init = qpow(init, n - 10);
for (int i = 1; i <= 10; ++i) ans += init.a[1][i] * (10 - i);
printf("%lld\n", ans % m);
}
}