洛谷-2044
思路
首先对与递推式\(x_n = (a * x_{n - 1} + c)\) % \(mod\),发现\(c\)的存在使得不能直接使用整数快速幂求出\(x_n\),因为\(x_n\)是关于\(a, c, x0\)的\(n\)次多项式。并且\(n\)是\(1e18\)大小的。
于是考虑使用矩阵快速幂加速,但是显然不能使用一维矩阵(没意义),考虑通过二维矩阵
\(\begin{pmatrix}
x_n & c
\end{pmatrix}\)
来得到关系式。(\(x_{n-1}\)和\(c\)均与\(x_n\)有关)
首先有
\[\begin{pmatrix} x_n & c \end{pmatrix} = \begin{pmatrix} x_{n - 1} & c \end{pmatrix} * \begin{pmatrix} A & B \\ C & D \end{pmatrix} \tag{1} \]将\((1)\)展开,有
\[\begin{cases} x_n = x_{n - 1} * A + c * C \\ c = x_{n - 1} * B + c * D \end{cases} \tag{2} \]由于\(x_n = a * x_{n - 1} + c\),替换\((2)\)中第一个方程的\(x_n\),得到
\[\begin{cases} a * x_{n - 1} + c = x_{n - 1} * A + c * C \\ c = x_{n - 1} * B + c * D \end{cases} \tag{3} \]由\((3)\)得到
\[\begin{pmatrix} A = a & B = 0 \\ C = 1 & D = 1 \end{pmatrix} \]再由于
\[\begin{pmatrix} x_n & c \end{pmatrix} = \begin{pmatrix} x_{n - 1} & c \end{pmatrix} * \begin{pmatrix} a & 0 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} x_{0} & c \end{pmatrix} * \begin{pmatrix} a & 0 \\ 1 & 1 \end{pmatrix} ^{n} \]可知,只需要求出
\(
\begin{pmatrix}
a & 0
\\
1 & 1
\end{pmatrix}
^{n}
\)
即可得到答案。
Code
#include <bits/stdc++.h>
using namespace std;
#define _u_u_ ios::sync_with_stdio(false), cin.tie(nullptr)
#define cf int _o_o_;cin>>_o_o_;for (int Case = 1; Case <= _o_o_;Case++)
#define SZ(x) (int)(x.size())
inline void _A_A_();
signed main() {_A_A_();return 0;}
using ll = long long;
#define int long long
int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int N = 2, M = 5010;
const int inf = 0x3f3f3f3f;
struct mat {
int m[N][N];
};
ll n, c, x0, g;
int mul(int a,int b) {
int res = 0;
a %= mod;
b %= mod;
while(b) {
if (b & 1) {
res = (res + a) % mod;
}
a = (a + a) % mod;
b >>= 1;
}
return res;
}
mat operator * (const mat&a, const mat&b) {
mat c;
memset(c.m, 0, sizeof c.m);
for (int i = 0;i < N;i++) {
for (int j = 0;j < N;j++) {
for (int k = 0;k < N;k++) {
c.m[i][j] = (c.m[i][j] + mul(a.m[i][k] , b.m[k][j])) % mod;
}
}
}
return c;
}
mat qpow(mat a, int b ) {
mat c;
memset(c.m, 0,sizeof c.m);
for (int i = 0;i < N;i++) c.m[i][i] = 1;
while (b) {
if (b & 1) {
c = c * a;
}
a = a * a;
b >>= 1;
}
return c;
}
inline void _A_A_() {
#ifdef LOCAL
freopen("in.in", "r", stdin);
#endif
_u_u_;
mat s;
memset(s.m, 0, sizeof s.m);
s.m[1][0] = s.m[1][1] = 1;
cin >> mod >> s.m[0][0] >> c >> x0 >> n >> g;
s = qpow(s, n);
int xn = (mul(s.m[0][0] , x0) + mul(c , s.m[1][0])) % mod;// 注意xn可能会大于mod,要取模。
cout << (xn) % g << "\n";
}
标签:2044,end,mat,int,begin,pmatrix,洛谷,mod
From: https://www.cnblogs.com/FanWQ/p/16888946.html