题解 CF575A 【Fibonotci】
xht
2019-12-07 22:37:50
> [CF575A Fibonotci](https://codeforc.es/contest/575/problem/A)
## 题意
- $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))$。
## 代码
```cpp
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;
}
```