【libreoj573】单枪匹马

发表于
https://loj.ac/problem/573

题目链接

【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 $ ） 。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#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;
}