P1397

这道题直接 $\operatorname{mod} \varphi(p)$ 的题解很多都是错的并且没有给出证明。

解题思路

首先这道题等价于求 $(A^{m-1}B)^{n-1}A^{m-1}$。

可以直接用高精度的矩阵快速幂，但是这里不讲。

不难发现在计算过程中矩阵一定是 $\begin{bmatrix}a&b\\0&1\end{bmatrix}$ 的形式。

所以现在问题转化为了计算型为 $A=\begin{bmatrix}a&b\\0&1\end{bmatrix}$ 的矩阵快速幂。

Part1

考虑讲矩阵对角化，也就是找到一个矩阵 $P$ 满足 $PAP^{-1}=B$ 是一个对角矩阵，也就是说:

$$B= \begin{bmatrix} \lambda_1&0\\ 0&\lambda_2 \end{bmatrix}$$

那么 $A^x=P^{-1}B^xP$。

证明：

$$\begin{aligned} P^{-1}BP&=P^{-1}(PAP^{-1})^xP\\ &=P^{-1}((PAP^{-1})(PAP^{-1})\dots(PAP^{-1}))P\\ &=P^{-1}(PAP^{-1}PAP^{-1}\dots PAP^{-1})P\\ &=P^{-1}(PA^xP^{-1})P\\ &=P^{-1}PA^xP^{-1}P\\ &=A^x \end{aligned}$$

接下来证明 $A^x=A^{x\operatorname{mod} \varphi(p)}\pmod{p}$。

只要证明 $B^x=B^{x\operatorname{mod} \varphi(p)}\pmod{p}$ 即可，显然：

$$\begin{aligned} B^x&= \begin{bmatrix} \lambda_1&0\\ 0&\lambda_2 \end{bmatrix}^x\\ &= \begin{bmatrix} \lambda_1^x&0\\ 0&\lambda_2^x \end{bmatrix}\\ &= \begin{bmatrix} \lambda_1^{x\operatorname{mod} \varphi(p)}&0\\ 0&\lambda_2^{x\operatorname{mod} \varphi(p)} \end{bmatrix}\\ &= \begin{bmatrix} \lambda_1&0\\ 0&\lambda_2 \end{bmatrix}^{x\operatorname{mod} \varphi(p)} \end{aligned}$$

Part2

现在来考虑什么时候能找到这么一个 $P$，先进行化简：

$$\begin{aligned} PAP^{-1}&= \begin{bmatrix} \lambda_1&0\\ 0&\lambda_2 \end{bmatrix} \\ PA&= \begin{bmatrix} \lambda_1&0\\ 0&\lambda_2 \end{bmatrix}P \\ \end{aligned}$$

设 $P=\begin{bmatrix}p_{1,1}&p_{1,2}\\p_{2,1}&p_{2,2}\end{bmatrix}$。

那么可以将上面等式变形为：

$$\begin{bmatrix} ap_{1,1}&bp_{1,1}+p_{1,2}\\ ap_{2,1}&bp_{2,1}+p_{2,2}\\ \end{bmatrix}= \begin{bmatrix} \lambda_1p_{1,1}&\lambda_1p_{1,2}\\ \lambda_2p_{2,1}&\lambda_2p_{2,2} \end{bmatrix}$$

化简得：

$$\begin{aligned} (a-1)p_{1,2}&=p_{1,1}b\\ (a-1)p_{2,2}&=p_{2,1}b \end{aligned}$$

所以当 $a\neq1$ 时可以对角化，这种情况用矩阵对角化就可以解决。

Part3

当 $a=1$ 时，发现就是每次加 $b$，那么很显然 $A^x=A^{x\operatorname{mod}p}\pmod p$，然后分类讨论即可。

代码实现

/*
* @Author: ftt2333
* @Email: ftt2333@126.com
* @LastEditTime: 2022-11-29 09:27:17
*/

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (auto i = (a); i <= (b); ++i)
#define per(i, a, b) for (auto i = (a); i >= (b); --i)
#define all(v) (v).begin(), (v).end()
#define szof(v) int((v).size())
using pii = pair<int, int>;
using ll = long long;

#define gc() getchar()
#define pc(c) putchar(c)
template <class T = int> T read() {
  T x = 0; char c = gc(); bool f = 0;
  for (; !isdigit(c); c = gc()) f = c == '-';
  for (; isdigit(c); c = gc()) x = x * 10 + c - 48;
  return f ? -x : x;
}
template <class T> void write(T x) {
  if (x >= 0) { if (x > 9) write(x / 10); pc(48 + x % 10); }
  else { pc('-'); if (x < -9) write(-(x / 10)); pc(48 - x % 10); }
}

const int N = 1e6 + 10, mod = 1e9 + 7;
struct mat {
  int a[2][2];
  mat() { memset(a, 0, sizeof(a)); }
};
mat operator*(const mat &a, const mat &b) {
  mat c;
  rep(i, 0, 1) rep(j, 0, 1) rep(k, 0, 1)
    (c.a[i][j] += 1ll * a.a[i][k] * b.a[k][j] % mod) %= mod;
  return c;
}
mat qpow(mat a, int b) {
  mat res;
  res.a[0][0] = 1, res.a[0][1] = 0;
  res.a[1][0] = 0, res.a[1][1] = 1;
  for (; b; b >>= 1, a = a * a)
    if (b & 1) res = res * a;
  return res;
}

char nstr[N], mstr[N];
int nlen, mlen, a, b, c, d, n, m;

int main() {
  scanf("%s%s", nstr + 1, mstr + 1);
  a = read(), b = read(), c = read(), d = read();
  int base0 = (a == 1 ? mod : mod - 1);
  nlen = strlen(nstr + 1), mlen = strlen(mstr + 1);
  rep(i, 1, mlen) {
    m = (10ll * m + mstr[i] - 48 + base0) % base0;
  }
  mat A, B;
  A.a[0][0] = a, A.a[0][1] = b;
  A.a[1][0] = 0, A.a[1][1] = 1;
  B.a[0][0] = c, B.a[0][1] = d;
  B.a[1][0] = 0, B.a[1][1] = 1;
  mat C;
  C.a[0][0] = 1, C.a[0][1] = 0;
  C.a[1][0] = 1, C.a[1][1] = 0;
  mat D = qpow(A, (m + base0 - 1) % base0) * B;
  int base1;
  if (D.a[0][0] == 1) base1 = mod;
  else base1 = mod - 1;
  rep(i, 1, nlen) {
    n = (10ll * n + nstr[i] - 48 + base1) % base1;
  }
  C = qpow(D, (n + base1 - 1) % base1) *
      qpow(A, (m + base0 - 1) % base0) * C;
  write(C.a[0][0]); pc(10);
}

hack 数据

in:

1145141919810 1000000007 2 1 1 2

ans:

283823589