【libreoj573】单枪匹马

题目链接

【libreoj573】单枪匹马

做法

可以证明直接计算不需要约分，可以直接取模。
证明：若 $\frac{x}{y}$ 中 $x, y$ 互质，则 $a + \frac{x}{y} = \frac{ay + x}{y}$ 中 $ay + x, y$ 互质（考虑辗转相除法中 gcd(X, Y) = gcd(Y, X % Y) (Y = y, X = ax + y) ）。
这样可以得到 $35 pts$ 。
设 $f[a_0 \dots a_n] = \frac{x[a_0 \dots a_n]}{y[a_0 \dots a_n]}$ ，则：

$$\frac{x[a_0 \dots a_n]}{y[a_0 \dots a_n]} = a_0 + \frac{y[a_1 \dots a_n]}{x[a_1 \dots a_n]} = \frac{y[a_1 \dots a_n] + a_0 x[a_1 \dots a_n]}{x[a_1 \dots a_n]}$$

由于这些都是最简分数，所以：

$$x[a_0 \dots a_n] = y[a_1 \dots a_n] + a_0x[a_1 \dots a_n]\\\\ y[a_0 \dots a_n] = x[a_1 \dots a_n]$$

可以得到：

$$x[a_0 \dots a_n] = x[a_2 \dots a_n] + a_0x[a_1 \dots a_n]\\\\ y[a_0 \dots a_n] = y[a_2 \dots a_n] + a_0y[a_1 \dots a_n]$$

考虑在图上的意义。在一个由 $n$ 个节点的有向图，$i$ 向 $i + 1$ 连边权为 $a_i$ 的边，向 $i + 2$ 连边权为 $1$ 的边。最后的值为 $1$ 到 $n$ 的路径边权乘积之和。显然这些边可以反向。可以得到：

$$x[a_0 \dots a_n] = a_nx[a_0 \dots a_{n-1}] + x[a_0 \dots a_{n - 2}]\\\\ y[a_0 \dots a_n] = a_ny[a_0 \dots a_{n-1}] + y[a_0 \dots a_{n - 2}]$$

然后这个东西可以矩阵转移。

$$A_i = \left[ \begin{matrix} a_i&1\\\\ 1&0 \end{matrix} \right], inv_i = \left[ \begin{matrix} 0&1\\\\ 1&mod - a_i \end{matrix} \right]\\\\ \left[ \begin{matrix} ansx\\\\ ansy \end{matrix} \right] = \prod_{i = l}^{r} A_i = (\prod_{i = 1}^{r}A_i) \times (\prod_{i = 1}^{l - 1}inv_i)$$

维护前缀积即可。
时间复杂度 $O(n + m)$ （矩阵乘法常数堪比一个 $\log$ ） 。

#include <bits/stdc++.h>
#define mp make_pair
#define fst first
#define snd second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 998244353;
const int N = 1000010;
int n, m, type, ansx, ansy;
int a[N], len;

inline int add(const int &x, const int &y) {
	return x + y < mod ? x + y : x + y - mod;
}
inline int sub(const int &x, const int &y) {
	return x - y < 0 ? x - y + mod : x - y;
}
inline int mul(const int &x, const int &y) { return (int)((ll)x * y % mod); }

struct mtrx {
	int a[2][2]; mtrx() { memset(a, 0, sizeof(a)); }
	inline mtrx operator*(const mtrx &yy)const {
		mtrx res = mtrx();
		for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++)
			for(int k = 0; k < 2; k++)
				res.a[i][j] = add(res.a[i][j], mul(a[i][k], yy.a[k][j]));
		return res;
	}
}; mtrx sum[N], inv[N], ans;

void insert(int x) {
	++len; mtrx mu; mu.a[1][0] = mu.a[0][1] = 1;
	mu.a[0][0] = x, sum[len] = sum[len - 1] * mu;
	mu.a[0][0] = 0, mu.a[1][1] = sub(0, x), inv[len] = mu * inv[len - 1];
}
int main() {
	scanf("%d%d%d", &n, &m, &type);
	sum[0].a[0][0] = sum[0].a[1][1] = 1;
	inv[0].a[0][0] = inv[0].a[1][1] = 1;
	for(int i = 1, x; i <= n; i++) scanf("%d", &x), insert(x);
	for(int opt, x, y; m; --m) {
		scanf("%d", &opt);
		if(opt == 1) {
			scanf("%d", &x); if(type) x = x ^ ansx ^ ansy;
			insert(x);
		}
		else {
			scanf("%d%d", &x, &y);
			if(type) x = x ^ ansx ^ ansy, y = y ^ ansx ^ ansy;
			ans = inv[x - 1] * sum[y];
			ansx = ans.a[0][0], ansy = ans.a[1][0];
			printf("%d %d\n", ansx, ansy);
		}
	}
	return 0;
}