[Easy-Medium] P11735 [集训队互测 2015] 胡策的数列

xiezheyuan2025/2/15约 991 字大约 5 分钟

简要题意

有一个数列 $a_i$ 满足：

对于 $i\geq2$ 有 $25a_i+20a_{i-1}=12a_{i-2}$ 。
$\forall i\in\mathbb{N},a_i\geq 0$ 。

给定一个长度为 $n$ 的序列 $a$ ，初始时全为 $0$ ，有 $m$ 次操作，支持：

1 l r x y $\forall i\in[l,r], a_i\gets a_{y+i-l}$ ，其中 $a_0=x$ 。保证 $a$ 序列通过既定条件可以唯一确定。
2 l r 求区间 $[l,r]$ 的和。答案对 $10^9+7$ 取模。

$1\leq n\leq 10^9,1\leq m\leq 10^5$ 。空间限制 $64\mathrm{MiB}$ 。

思路

先来解递推式。

对于 $25a_i+20a_{i-1}=12a_{i-2}$ ，其特征方程为 $25a_i\cdot r^i+20a_i\cdot r^{i-1}=12\cdot r^{i-2}$ ，即 $25r^2+20r-12=0$ 。

解得 $r_1=\frac{2}{5},r_2=-\frac{6}{5}$ 。故通项公式形如 $a_n=A\cdot (\frac{2}{5})^n+B\cdot (-\frac{6}{5})^n$ 。由于 $a_0$ 已经确定，所以两系数和 $A+B=a_0$ 已经确定。

现在考虑解出 $A,B$ ，由于题目中要求 $a_i\geq 0$ 。我们来证明若 $B\neq0$ ，则一定存在 $a_i<0$ 。

为了方便，假定 $B>0$ ， $B<0$ 是类似的。当 $n$ 为奇数时， $(-\frac{6}{5})^n$ 为负数，所以 $A$ 必为正数。而当 $n>\log_3 \frac{A}{B}$ 时，有 $A\cdot (\frac{2}{5})^n<B (-\frac{6}{5})^n$ ，故存在 $a_i\geq0$ 。

所以 $B=0$ ，则 $A=a_0$ ，通项公式形如 $a_0\cdot (\frac{2}{5})^n$ 是等比数列。

区间覆盖等差数列，区间求和，可以用动态开点线段树完成。具体实现我相信做这道题的同学应该都比较熟悉，就不阐述了。

然后就被卡空了。

（第一次被卡空成这样的我）

有两个比较好的空间优化：

询问时，如果到达的点是叶子结点，并且可以向下递归，可以直接用未下传的标记计算答案。
左节点和右节点可以只保存一个，生成节点时先生成左节点和右节点，来让编号连续。

代码

#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
using namespace std;

constexpr int mod = 1e9 + 9;
int Add(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }
int Sub(int x, int y){ return (x - y) < 0 ? (x - y + mod) : (x - y); }
int Mul(int x, int y){ return 1ll * x * y % mod; }

template<int BD>
struct lightspeed_pow {
    int f[BD + 5], g[(mod / BD) + 5];
    void init(int base){
        f[0] = g[0] = 1;
        for(int i=1;i<=BD;i++) f[i] = Mul(f[i - 1], base);
        for(int i=1;i<=mod/BD;i++) g[i] = Mul(g[i - 1], f[BD]);
    }
    int ask(int x){ return x %= (mod - 1), Mul(g[x / BD], f[x % BD]); }
};

lightspeed_pow<31623> lsp;

const int N = 5.2e6 + 5, BASE = 400000004, INC_INV = 333333338;
int t[N], tag[N], ls[N], tot;

int calc(int ratio, int len){
    return Mul(Mul(ratio, Sub(1, lsp.ask(len))), INC_INV);
}

void mktag(int v, int i, int l, int r){ tag[i] = v, t[i] = calc(v, r - l + 1); }

void pushdown(int i, int l, int r){
    if(!tag[i]) return;
    mktag(tag[i], ls[i], l, mid);
    mktag(Mul(tag[i], lsp.ask(mid - l + 1)), ls[i] + 1, mid + 1, r);
    tag[i] = 0;
}

int update(int ql, int qr, int v, int i, int l, int r){
    if(ql <= l && r <= qr) return mktag(v, i, l, r), r - l + 1;
    if(!ls[i]) ls[i] = ++tot, ++tot;
    pushdown(i, l, r);
    int tmp = 0;
    if(ql <= mid) tmp += update(ql, qr, v, ls[i], l, mid), v = Mul(v, lsp.ask(tmp));
    if(qr > mid) tmp += update(ql, qr, v, ls[i] + 1, mid + 1, r);
    t[i] = Add(t[ls[i]], t[ls[i] + 1]);
    return tmp;
}

int query(int ql, int qr, int i, int l, int r){
    if(ql <= l && r <= qr) return t[i];
    if(!ls[i]){
        return Sub(calc(tag[i], min(qr - l + 1, r - l + 1)), calc(tag[i], max(ql - l, 0)));
    }
    pushdown(i, l, r);
    int ans = 0;
    if(ql <= mid) ans = Add(ans, query(ql, qr, ls[i], l, mid));
    if(qr > mid) ans = Add(ans, query(ql, qr, ls[i] + 1, mid + 1, r));
    return ans;
}

int n, m;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    lsp.init(BASE);
    int rt = 1, lastans = 0; tot = 1;
    while(m--){
        int op, l, r, x, y;
        cin >> op >> l >> r;
        l ^= lastans, r ^= lastans;
        if(op == 1){
            cin >> x >> y;
            update(l, r, Mul(x, lsp.ask(y)), rt, 1, n);
        }
        else cout << (lastans = query(l, r, rt, 1, n)) << '\n';
    }
    cerr << tot << '\n';
    return 0;
}

// Written by xiezheyuan

Submission。