多少有点混乱邪恶。
题意：给出递推式：
\[a_1=b_1=c_1=1\\
a_2=b_2=c_2=3\\
\begin{aligned}
a_k&=p\times a_{k-1}+q\times a_{k-2}&+b_{k-1}+c_{k-1}&+r(k-2)^2+t(k-2)+1\\
b_k&=u\times b_{k-1}+v\times b_{k-2}&+a_{k-1}+c_{k-1}&+w^{k-2}\\
c_k&=x\times c_{k-1}+y\times c_{k-2}&+a_{k-1}+b_{k-1}&+z^{k-2}+k
\end{aligned}
\]
求 \(a_n,b_n,c_n\) 模 \(m\) 的值
\(4\le n\le 10^{16},2\le m\le 10^{16}\)，其他数据 \(\le 100\)
思路：
先把递推式改写成 \(a_{k+1}=\cdots\) 的形式：
\[\begin{aligned}
a_{k+1}&=p\times a_k+q\times a_{k-1}&+b_{k}+c_{k}&+r(k-1)^2+t(k-1)+1\\
b_{k+1}&=u\times b_{k}+v\times b_{k-1}&+a_{k}+c_{k}&+w^{k-1}\\
c_{k+1}&=x\times c_{k}+y\times c_{k-1}&+a_{k}+b_{k}&+z^{k-1}+k+1
\end{aligned}
\]
考虑维护 \(a_k,a_{k-1},b_k,b_{k-1},c_k,c_{k-1},(k-1)^2,k-1,w^{k-1},z^{k-1},1\)，有递推式：
\[\begin{bmatrix}
p & q & 1 & 0 & 1 & 0 & r & t & 0 & 0 & 1\\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & u & v & 1 & 0 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 0 & x & y & 0 & 1 & 0 & 1 & 2\\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & w & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & z & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1
\end{bmatrix}\begin{bmatrix}
a_k\\ a_{k-1}\\
b_k\\ b_{k-1}\\
c_k\\ c_{k-1}\\
(k-1)^2\\ k-1\\
w^{k-1}\\ z^{k-1}\\
1
\end{bmatrix}=\begin{bmatrix}
a_{k+1}\\ a_{k}\\
b_{k+1}\\ b_{k}\\
c_{k+1}\\ c_{k}\\
k^2\\ k\\
w^{k}\\ z^{k}\\
1
\end{bmatrix}
\]
然后就做完了，答案即为
\[\begin{bmatrix}
p & q & 1 & 0 & 1 & 0 & r & t & 0 & 0 & 1\\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & u & v & 1 & 0 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 0 & x & y & 0 & 1 & 0 & 1 & 2\\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & w & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & z & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1
\end{bmatrix}^{n-2}
\begin{bmatrix}
3\\ 1\\
3\\ 1\\
3\\ 1\\
1\\ 1\\
w\\ z\\
1
\end{bmatrix}=\begin{bmatrix}
a_n\\ a_{n-1}\\
b_n\\ b_{n-1}\\
c_n\\ c_{n-1}\\
(n-1)^2\\ n-1\\
w^{n-1}\\ z^{n-1}\\
1
\end{bmatrix}
\]
#include <iostream>
using namespace std;
using LL = long long;
using i128 = __int128_t;
template <int kN, int kM>
struct M {
i128 a[kN + 1][kM + 1];
M() { fill(a[0], a[kN + 1], 0); }
};
LL n, m;
int p, q, r, t, u, v, w, x, y, z;
template <int kNa, int kMa, int kMb>
const M<kNa, kMb> operator*(const M<kNa, kMa> &x, const M<kMa, kMb> &y) {
M<kNa, kMb> s;
for (int i = 1; i <= kNa; ++i) {
for (int k = 1; k <= kMa; ++k) {
for (int j = 1; j <= kMb; ++j) {
s.a[i][j] += x.a[i][k] * y.a[k][j];
}
}
}
for (int i = 1; i <= kNa; ++i) {
for (int j = 1; j <= kMb; ++j) {
s.a[i][j] %= m;
}
}
return s;
}
template <int kN>
M<kN, kN> P(M<kN, kN> b, LL e) {
M<kN, kN> s;
for (int i = 1; i <= kN; ++i) {
s.a[i][i] = 1;
}
for (; e; e >>= 1, b = b * b) {
if (e & 1) {
s = s * b;
}
}
return s;
}
M<11, 11> b;
M<11, 1> s;
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
cin >> p >> q >> r >> t;
cin >> u >> v >> w;
cin >> x >> y >> z;
b.a[1][1] = p, b.a[1][2] = q, b.a[1][3] = b.a[1][5] = b.a[2][1] = 1;
b.a[1][7] = r, b.a[1][8] = t, b.a[1][11] = 1;
b.a[3][3] = u, b.a[3][4] = v, b.a[3][1] = b.a[3][5] = b.a[4][3] = 1;
b.a[3][9] = 1;
b.a[5][5] = x, b.a[5][6] = y, b.a[5][1] = b.a[5][3] = b.a[6][5] = 1;
b.a[5][8] = b.a[5][10] = 1, b.a[5][11] = 2;
b.a[7][7] = 1, b.a[7][8] = 2, b.a[7][11] = 1;
b.a[8][8] = 1, b.a[8][11] = 1;
b.a[9][9] = w, b.a[10][10] = z, b.a[11][11] = 1;
s.a[1][1] = s.a[3][1] = s.a[5][1] = 3;
s.a[2][1] = s.a[4][1] = s.a[6][1] = 1;
s.a[7][1] = s.a[8][1] = 1;
s.a[9][1] = w, s.a[10][1] = z, s.a[11][1] = 1;
M<11, 1> r = P(b, n - 2) * s;
cout << "nodgd " << LL(r.a[1][1]) << '\n';
cout << "Ciocio " << LL(r.a[3][1]) << '\n';
cout << "Nicole " << LL(r.a[5][1]);
return 0;
}