当我跨过沉沦的一切
向着永恒开战的时候
你是我的军旗

官方题解是什么神仙东西看啊看不懂的。

Link

考虑我们维护一个分数类 (x, y) 表示 \frac x y 。假设 f(a_1, a_2, ..., a_n) = \frac x y 那么 f(a_0, a_1, a_2, ..., a_n) = \frac {a_0 x + y} {x} 。可以考虑用矩阵来维护转移。

定义将 (x, y)(a x + y, x) 的转移为

\left[\begin{matrix} a & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} x \\ y \\ \end{matrix}\right] = \left[\begin{matrix} ax + y \\ x \end{matrix}\right]

反之,从 (ax + y, x)(x, y) 的转移为

\left[\begin{matrix} 0 & 1 \\ 1 & -a \\ \end{matrix}\right] \left[\begin{matrix} ax + y \\ x \\ \end{matrix}\right] = \left[\begin{matrix} x \\ y \\ \end{matrix}\right]

那么

\begin{aligned} Ans_{l, r} &= \left[\begin{matrix} a_l & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} a_{l + 1} & 1 \\ 1 & 0 \\ \end{matrix}\right] \cdots \left[\begin{matrix} a_r & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} 1 \\ 0 \end{matrix}\right] \\ &= \left[\begin{matrix} 0 & 1 \\ 1 & -a_{l - 1} \\ \end{matrix}\right] \left[\begin{matrix} 0 & 1 \\ 1 & -a_{l - 2} \\ \end{matrix}\right] \cdots \left[\begin{matrix} 0 & 1 \\ 1 & -a_1 \\ \end{matrix}\right] \left[\begin{matrix} a_1 & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} a_2 & 1 \\ 1 & 0 \\ \end{matrix}\right] \cdots \left[\begin{matrix} a_r & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} 1 \\ 0 \end{matrix}\right] \end{aligned}

可以分别处理出前缀和

\begin{aligned} F_n &= \left[\begin{matrix} a_1 & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} a_2 & 1 \\ 1 & 0 \\ \end{matrix}\right] \cdots \left[\begin{matrix} a_n & 1 \\ 1 & 0 \\ \end{matrix}\right] \\ G_n &= \left[\begin{matrix} 0 & 1 \\ 1 & -a_{n} \\ \end{matrix}\right] \left[\begin{matrix} 0 & 1 \\ 1 & -a_{n - 1} \\ \end{matrix}\right] \cdots \left[\begin{matrix} 0 & 1 \\ 1 & -a_1 \\ \end{matrix}\right] \end{aligned}

代码:

// =================================
//   author: memset0
//   date: 2019.07.08 13:48:12
//   website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
#define rep(i, l, r) for (int (i) = (l), __lim = (r); (i) <= __lim; (i)++)
#define for_each(i, a) for (size_t i = 0, __lim = a.size(); i < __lim; ++i)
namespace ringo {

template <class T> inline void read(T &x) {
  x = 0; char c = getchar(); bool f = 0;
  while (!isdigit(c)) f ^= c == '-', c = getchar();
  while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
  if (f) x = -x;
}
template <class T> inline void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) print(x / 10);
  putchar('0' + x % 10);
}
template <class T> inline void print(T x, char c) { print(x), putchar(c); }
template <class T> inline void print(T a, int l, int r, std::string s = "") {
  if (s != "") std::cout << s << ": ";
  for (int i = l; i <= r; i++) print(a[i], " \n"[i == r]);
}

const int N = 1e6 + 10, mod = 998244353;
int n, m, l, r, opt, type, lastans, a[N];

struct matrix {
  int a00, a01, a10, a11;
  inline void out() const {
    printf("[%d %d %d %d]", a00, a10, a01, a11);
  }
} ans, f[N], g[N], x[N], y[N];

inline matrix getF(int a) { return (matrix){a, 1, 1, 0}; }
inline matrix getG(int a) { return (matrix){0, 1, 1, mod - a}; }

inline matrix operator*(const matrix &x, const matrix &y) {
  return (matrix){
    (int)((1ll * x.a00 * y.a00 + 1ll * x.a01 * y.a10) % mod),
    (int)((1ll * x.a00 * y.a01 + 1ll * x.a01 * y.a11) % mod),
    (int)((1ll * x.a10 * y.a00 + 1ll * x.a11 * y.a10) % mod),
    (int)((1ll * x.a10 * y.a01 + 1ll * x.a11 * y.a11) % mod)
  };
}

void main() {
  read(n), read(m), read(type);
  for (int i = 1; i <= n; i++) read(a[i]);
  f[0] = g[0] = {1, 0, 0, 1};
  for (int i = 1; i <= n; i++) {
    f[i] = f[i - 1] * getF(a[i]);
    g[i] = getG(a[i]) * g[i - 1];
  }
  // for (int i = 1; i <= n; i++) f[i].out(), putchar(" \n"[i == n]);
  // for (int i = 1; i <= n; i++) g[i].out(), putchar(" \n"[i == n]);
  for (int i = 1; i <= m; i++) {
    read(opt);
    if (opt == 1) {
      read(a[++n]);
      if (type) a[n] ^= lastans;
      f[n] = f[n - 1] * getF(a[n]);
      g[n] = getG(a[n]) * g[n - 1];
    } else {
      read(l), read(r);
      if (type) l ^= lastans, r ^= lastans;
      ans = g[l - 1] * f[r] * (matrix){1, 0, 0, 0};
      // g[l - 1].out(), f[r].out(), ans.out(), putchar('\n');
      print(ans.a00, ' '), print(ans.a10, '\n');
      lastans = ans.a00 ^ ans.a10;
    }
  }
}

} signed main() {
#ifdef memset0 
  freopen("1.in", "r", stdin);
#endif
  return ringo::main(), 0;
}

矩阵乘法 矩阵求逆 Favorite 差分与前缀和

LOJ575 「LibreOJ NOI Round #2」不等关系
上一篇 «
洛谷4035 [JSOI2008]球形空间产生器
» 下一篇