CF575A Fibonotci 题解

CF575A Fibonotci

题意

• $s_{0\dots +\infty}$ 是一个正整数序列。
• 给定 $s_{0 \dots n - 1}$，对于 $i \ge n$，有 $m$ 个 $i$ 给定 $s_i$，剩下的 $i$ 满足 $s_i = s_{i \bmod n}$。
• $f_{0 \dots +\infty}$ 同样是一个正整数序列。
• 给定 $f_0,f_1$，对于 $i \ge 2$，$f_i = s_{i-1}f_{i-1} + s_{i-2}f_{i-2}$。
• 求 $f_k \bmod p$。
• $n,m \le 5 \times 10^4$，$k \le 10^{18}$，$s_i,p \le 10^9$。

题解

首先考虑 $m = 0$ 的情况。

由于 $f_i = s_{i-1}f_{i-1} + s_{i-2}f_{i-2}$，有：

$$\begin{bmatrix} f_{i-2} & f_{i-1} \end{bmatrix} \times \begin{bmatrix} 0 & s_{i-2} \\\\ 1 & s_{i-1} \end{bmatrix} = \begin{bmatrix} f_{i-1} & f_i \end{bmatrix}$$

因此：

$$\begin{bmatrix} f_{0} & f_{1} \end{bmatrix} \times \prod_{i=1}^{n} \begin{bmatrix} 0 & s_{i-1} \\\\ 1 & s_{i \bmod n} \end{bmatrix} = \begin{bmatrix} f_{n} & f_{n+1} \end{bmatrix}$$

于是可以矩阵快速幂，最后一段可以暴力转移。

考虑 $m \ne 0$ 时，线段树维护矩阵乘积。

每次只会修改两个矩阵，因此一共只有 $\mathcal O(m)$ 个单点修改。

因此可以在没有特殊值的周期内用矩阵快速幂转移，有特殊值的周期内单点修改之后再转移再修改回去。

总时间复杂度 $\mathcal O(n + m (\log k + \log n))$。

代码

const int N = 5e4 + 7;
ll k, o;
int n, m, x;
modint s[N];

struct mt {
	int n, m; modint a[2][2];
	inline mt() {}
	inline mt(int n, int m) : n(n), m(m) { memset(a, 0, sizeof(a)); }
	inline friend mt operator * (mt x, mt y) {
		mt z(x.n, y.m);
		for (int i = 0; i < z.n; i++)
			for (int k = 0; k < x.m; k++)
				for (int j = 0; j < z.m; j++)
					z.a[i][j] += x.a[i][k] * y.a[k][j];
		return z;
	}
} a[N], b[N], f;

inline void ksm(mt x, ll y, mt &z) {
	while (y) {
		if (y & 1) z = z * x;
		x = x * x, y >>= 1;
	}
}

struct Q {
	ll x, k; modint y;
	inline bool operator < (Q o) { return x < o.x; }
} q[N<<1];

struct T {
	int l, r; mt x;
} t[N<<2];

inline void build(int p, int l, int r) {
	t[p].l = l, t[p].r = r;
	if (l == r) return t[p].x = a[l], void();
	build(ls, l, md), build(rs, md + 1, r);
	t[p].x = t[ls].x * t[rs].x;
}

inline void chg(int p, int x, mt y) {
	if (t[p].l == t[p].r) return t[p].x = y, void();
	chg(x <= md ? ls : rs, x, y), t[p].x = t[ls].x * t[rs].x;
}

int main() {
	rd(k), rd(P), rd(n);
	for (int i = 0; i < n; i++) rd(x), s[i] = x % P;
	for (int i = 1; i <= n; i++) a[i] = mt(2, 2), a[i].a[0][1] = s[i-1], a[i].a[1][1] = s[i%n], a[i].a[1][0] = 1, b[i] = a[i];
	build(1, 1, n), rd(m);
	for (int i = 1; i <= m; i++) rd(q[i].x), q[m+i].x = q[i].x + 1, q[i].k = 1, rd(x), q[m+i].y = q[i].y = x % P;
	sort(q + 1, q + (m <<= 1) + 1);
	while (m && q[m].x > k) --m;
	f = mt(1, 2), f.a[0][1] = 1;
	for (int i = 1, j = 1; i <= m; i = ++j) {
		ll w = (q[i].x - 1) / n;
		while (j < m && w == (q[j+1].x - 1) / n) ++j;
		ksm(t[1].x, w - o, f), o = w;
		for (int k = i; k <= j; k++) {
			int d = (q[k].x - 1) % n + 1;
			b[d].a[q[k].k][1] = q[k].y, chg(1, d, b[d]);
		}
		if (w == k / n) break;
		f = f * t[1].x, o = w + 1;
		for (int k = i; k <= j; k++) {
			int d = (q[k].x - 1) % n + 1;
			chg(1, d, b[d] = a[d]);
		}
	}
	ll w = k / n;
	ksm(t[1].x, w - o, f);
	for (int i = 1, d = k % n; i <= d; i++) f = f * b[i];
	print(f.a[0][0]);
	return 0;
}