然而查了两个小时都没看出错误来……太蒟蒻力（悲
by JustPureH2O @ 2024-01-23 21:15:08
我记得要写龟速乘来着 @[JustPureH2O](/user/612722)
by dsy081101 @ 2024-01-23 21:20:14
@[dsy081101](/user/371780) 看错了抱歉（）
by dsy081101 @ 2024-01-23 21:22:16
@[JustPureH2O](/user/612722) 已解决，在矩阵乘法的时候取模取错了：[记录](https://www.luogu.com.cn/record/144038850)
```cpp
#include <bits/stdc++.h>
#define N 15
using namespace std;
typedef long long ll;
ll MOD;
struct Matrix {
ll mat[N][N];
Matrix() {
memset(mat, 0, sizeof mat);
}
void I() {
for (int i = 1; i <= 2; i++) mat[i][i] = 1;
}
};
ll qmul(ll a, ll b) {
ll res = 0;
while (b) {
if (b & 1) res = (res + a) % MOD;
a = (a + a) % MOD;
b >>= 1;
}
return res;
}
Matrix operator *(const Matrix &l, const Matrix &r) {
Matrix res;
for (int k = 1; k <= 2; k++) {
for (int i = 1; i <= 2; i++) {
for (int j = 1; j <= 2; j++) {
(res.mat[i][j] += qmul(l.mat[i][k], r.mat[k][j]) )%= MOD;
}
}
}
return res;
}
Matrix qpow(Matrix a, ll b) {
Matrix res;
res.I();
while (b) {
if (b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
//void out(Matrix m) {
// for (int i = 1; i <= 2; cout<<endl, i ++) {
// for (int j = 1; j <= 2; j++) {
// cout<<m.mat[i][j]<<' ';
// }
// }
//}
int main() {
ll a, c, x0, n, g;
cin>>MOD>>a>>c>>x0>>n>>g;
Matrix A, M;
A.mat[1][1] = x0;
A.mat[1][2] = c;
M.mat[1][1] = a;
M.mat[2][1] = M.mat[2][2] = 1;
A = A * qpow(M, n);
cout<<(A.mat[1][1] % g)<<endl;
return 0;
}
```
by dsy081101 @ 2024-01-23 21:24:56
@[JustPureH2O](/user/612722) 一般这种题
```cpp
res.mat[i][j] += qmul(l.mat[i][k], r.mat[k][j]) % MOD;
```
要写成这样子
```cpp
res.mat[i][j] += qmul(l.mat[i][k], r.mat[k][j]) % MOD;
res.mat[i][j] %= MOD;
```
by GGapa @ 2024-01-23 21:29:25
@[dsy081101](/user/371780) %%%，已解决谢谢
by JustPureH2O @ 2024-01-24 08:04:59
@[GGapa](/user/597060) 这回长记性了orz
by JustPureH2O @ 2024-01-24 08:05:21
@[GGapa](/user/597060) %%%
by gaoyuxiang10086 @ 2024-03-21 20:18:14