我的式子：
\begin{bmatrix}
1&0&0&0&0&0&0&\cdots&0&0\\
1&1&0&0&0&0&0&\cdots&0&0\\
1&2&1&0&0&0&0&\cdots&0&0\\
0&0&0&0&1&0&0&\cdots&0&0\\
0&0&0&0&0&1&0&\cdots&0&0\\
&&&&&\vdots\\
0&0&0&0&0&0&0&\cdots&0&1\\
p&q&r&c_{n}&c_{n-1}&c_{n-2}&c_{n-3}&\cdots&c_{2}&c_{1}
\end{bmatrix}
\times
\begin{bmatrix}
1\\
i\\
i^2\\
a_{i-n}\\
a_{i-n+1}\\
\cdots\\
a_{i-2}\\
a_{i-1}\\
\end{bmatrix}
=
\begin{bmatrix}
1\\
i+1\\
(i+1)^2\\
a_{i-n+1}\\
a_{i-n+2}\\
\cdots\\
a_{i-1}\\
a_{i}\\
\end{bmatrix}
代码：
#include <bits/stdc++.h>
// #define int long long
using lint = long long;
const int N = 50;
const int MOD = 1e9 + 7;
template<typename T> // T 表示矩阵存的值的类型
struct Matrix {
size_t n, m; // n 为行数，m 为列数
std::vector<std::vector<T>> a;
Matrix(size_t _n = 0, size_t _m = 0) : n(_n), m(_m) {
a.resize(_n);
for (size_t i = 0; i < _n; ++i)
a[i].resize(_m);
}
Matrix(const std::vector<std::vector<T>> &_a) : n(_a.size()), m(_a[0].size()), a(_a) {}
void build() { for (size_t i = 0; i < n; ++i) a[i][i] = 1; }
void resize(size_t _n = 0, size_t _m = 0) {
n = _n, m = _m;
a = std::vector<std::vector<T>>(n, std::vector<T>(m));
}
Matrix<T> operator*(const Matrix<T> &A) {
if (m != A.n) throw "Error";
Matrix<T> res(n, A.m);
for (size_t i = 0; i < n; ++i) // 枚举最终矩阵的行
for (size_t j = 0; j < A.m; ++j) // 枚举最终矩阵的列
for (size_t k = 0; k < m; ++k) // 枚举 A 的列（B 的行）
(res.a[i][j] += a[i][k] * A.a[k][j] % MOD) %= MOD; // 实际实现中可能需要取模
return res;
}
void operator*=(const Matrix<T> &A) {
*this = *this * A;
}
};
template <typename T>
std::istream &operator>>(std::istream &is, Matrix<T> &A) { // 读入矩阵
for (size_t i = 0; i < A.n; ++i)
for (size_t j = 0; j < A.m; ++j)
is >> A.a[i][j];
return is;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const Matrix<T> &A) { // 输出矩阵
for (size_t i = 0; i < A.n; ++i) {
for (size_t j = 0; j < A.m; ++j)
os << A.a[i][j] << ' ';
os << '\n';
}
return os;
}
template <typename T>
Matrix<T> qpow(Matrix<T> &P, size_t b) { // 矩阵快速幂
Matrix<T> ans(P.a.size(), P.a.size());
ans.build();
for (; b; b >>= 1) {
if (b & 1) ans *= P;
P *= P;
}
return ans;
}
int n, p, q, r, c[N];
long long k;
Matrix<lint> S, T, ans;
void init_S() {
S.resize(n + 3, 1);
S.a[0][0] = 1, S.a[1][0] = n, S.a[2][0] = n * n;
for (int i = 3; i < n + 3; ++i)
std::cin >> S.a[i][0];
}
void init_T() {
T.resize(n + 3, n + 3);
T.a[0][0] = T.a[1][0] = T.a[1][1] = T.a[2][0] = T.a[2][2] = 1;
T.a[2][1] = 2;
for (int i = 3; i < n + 2; ++i) T.a[i][i + 1] = 1;
for (int i = 1; i <= n; ++i) std::cin >> c[i];
std::cin >> p >> q >> r;
T.a[n + 2][0] = p, T.a[n + 2][1] = q, T.a[n + 2][2] = r;
for (int i = 1; i <= n; ++i)
T.a[n + 2][i + 2] = c[n - i + 1];
}
signed main() {
std::cin >> n >> k;
init_S(), init_T();
if (k < n)
return std::cout << S.a[k + 3][0] << '\n', 0;
auto ans = qpow(T, k - n + 1) * S;
std::cout << ans.a[n + 2][0] << '\n';
return 0;
}
目前信友队 AC，但是 CF 上 WA on 23，提交记录。
求助洛谷可以给关注
