Visits: 240

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;
}