这个题太典了,gpt做不对我会怀疑gpt的训练数据有问题.

user

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
递增子序列
对于任意i>=1，序列a_i满足a_i=153^i \bmod 10\ 000\ 019。该序列的一开始几项为：153, 23409, 3581577, 7980255, 976697, 9434375, \dots

考虑该序列长度为4的递增子序列。只看上面列出的几项，这样的子序列包括：
153, 23409, 976697, 9434375
153, 23409, 3581577, 7980255
...

记s(n)为序列a_i的前n项中，此类子序列的各项之和。因此S(6)=94513710。已知S(100)=4465488724217。

求S(10^6)并对1\ 000\ 000\ 007取余。

我的思路:树状数组.
设dp[i][l]表示以a_i结尾,长度为l的序列的个数.
从小到大枚举l,离散化a_i然后用树状数组维护即可.
请给我c++代码实现.

gpt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
你的思路是**对的，但需要补充一个关键点**：
这里要求的不是「长度为 4 的递增子序列的个数」，而是**这些子序列中“所有元素的总和”**。

因此 **仅有 dp[i][l] = 个数 不够**，还需要同时维护：

* `cnt[i][l]`：以 `a[i]` 结尾、长度为 `l` 的递增子序列个数
* `sum[i][l]`：这些子序列中 **所有元素的和**

---

## 一、状态设计（核心）

对每个长度 `l = 1..4`，用一个树状数组维护两类信息：

* `BIT_cnt[l]`：某个值结尾的长度 `l` 子序列的**个数**
* `BIT_sum[l]`：某个值结尾的长度 `l` 子序列的**元素总和**

### 转移

设当前值是 `x = a[i]`（离散化后为 `pos`）

#### 1️⃣ 长度为 1
1
2
cnt = 1
sum = x
1
#### 2️⃣ 长度 ≥ 2
1
2
cnt = query_cnt(l-1, < x)
sum = query_sum(l-1, < x) + cnt * x
1
2
3
4
5
6
7
8
9
10
意思是：

* 每个旧序列都加上当前的 `x`
* 所以总和要额外加 `cnt * x`

---

## 二、树状数组设计

每个 BIT 节点存一个 `(cnt, sum)` 对：
1
2
3
struct Node {
    long long cnt, sum;
};
1
2
3
4
5
6
7
8
9
10
11
12
---

## 三、复杂度分析

* n = 1e6
* 每个元素更新 4 次 BIT
* 时间复杂度：`O(4 * n * log n)` ✅
* 空间：`4 * 2 * BIT_size`，可接受

---

## 四、完整 C++ 实现（可直接用）
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;

static const int MOD = 1'000'000'007;
static const int MAXV = 10'000'019;

struct BIT {
    int n;
    vector<long long> cnt, sum;

    BIT(int n = 0) : n(n), cnt(n + 1), sum(n + 1) {}

    void add(int idx, long long c, long long s) {
        for (; idx <= n; idx += idx & -idx) {
            cnt[idx] = (cnt[idx] + c) % MOD;
            sum[idx] = (sum[idx] + s) % MOD;
        }
    }

    pair<long long, long long> query(int idx) {
        long long c = 0, s = 0;
        for (; idx > 0; idx -= idx & -idx) {
            c = (c + cnt[idx]) % MOD;
            s = (s + sum[idx]) % MOD;
        }
        return {c, s};
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    const int N = 1'000'000;

    // 生成序列
    vector<int> a(N + 1);
    long long cur = 1;
    for (int i = 1; i <= N; ++i) {
        cur = cur * 153 % MAXV;
        a[i] = (int)cur;
    }

    // 离散化
    vector<int> vals(a.begin() + 1, a.end());
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    auto get_id = [&](int x) {
        return lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1;
    };

    int M = vals.size();

    // 4 层 BIT
    BIT bit_cnt[5], bit_sum[5];
    for (int i = 1; i <= 4; ++i) {
        bit_cnt[i] = BIT(M);
        bit_sum[i] = BIT(M);
    }

    long long answer = 0;

    for (int i = 1; i <= N; ++i) {
        int x = a[i];
        int id = get_id(x);

        // 从大到小枚举长度，防止本轮污染
        for (int len = 4; len >= 2; --len) {
            auto [c, s] = bit_cnt[len - 1].query(id - 1);
            if (c == 0) continue;

            long long new_sum = (s + c * x) % MOD;
            bit_cnt[len].add(id, c, new_sum);

            if (len == 4) {
                answer = (answer + new_sum) % MOD;
            }
        }

        // len = 1
        bit_cnt[1].add(id, 1, x);
    }

    cout << answer << '\n';
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
---

## 五、几点重要提醒

✔ **长度必须倒序更新（4 → 1）**
✔ **sum 转移一定要加 `cnt * a[i]`**
✔ 使用 `long long + mod` 防止溢出
✔ 本题是 **“递增（严格）”**，所以用 `< x`

---

如果你愿意，我可以再帮你：

* 🔥 做 **内存压缩版本**
* 🚀 改成 **模板化 LIS-k**
* 🧠 讲清楚为什么 `S(6)=94513710`
* ⚡ 或分析为什么这道题能跑到 1e6 而不卡

随时说 👍