Problem 733: Ascending Subsequences

Mathematical Analysis

Counting with Weighted Sums

For each ascending subsequence $(a_{i_1}, a_{i_2}, a_{i_3}, a_{i_4})$, its contribution to $S$ is $a_{i_1} + a_{i_2} + a_{i_3} + a_{i_4}$.

We can decompose: the contribution of $a_j$ at position $k$ (1st, 2nd, 3rd, or 4th element) equals $a_j$ times the number of ascending subsequences where $a_j$ occupies position $k$.

BIT/Fenwick Tree Approach

Define arrays for $j = 1, \ldots, n$:

• $c_k(j)$ = number of ascending subsequences of length $k$ ending at $j$.
• $s_k(j)$ = sum of all elements in all ascending subsequences of length $k$ ending at $j$.

Recurrence:

These prefix sums over $a_i < a_j$ can be computed efficiently using a Fenwick tree (BIT) indexed by the value $a_i$ (after coordinate compression).

Editorial

Sum of all elements in all ascending subsequences of length 4. Uses Fenwick trees for efficient prefix sum queries. We coordinate-compress the values to $[1, n]$. We then maintain 4 Fenwick trees for $c_1, c_2, c_3, c_4$ (counts) and 4 for $s_1, s_2, s_3, s_4$ (sums). Finally, process elements left to right. For each $a_j$.

Pseudocode

Generate all $a_i$ for $i = 1, \ldots, n$
Coordinate-compress the values to $[1, n]$
Maintain 4 Fenwick trees for $c_1, c_2, c_3, c_4$ (counts) and 4 for $s_1, s_2, s_3, s_4$ (sums)
Process elements left to right. For each $a_j$:
Query prefix sum of $c_{k-1}$ and $s_{k-1}$ for values $< a_j$
Update $c_k$ and $s_k$ at position $a_j$
Final answer: $S = \sum_j s_4(j)$

Verification

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity Analysis

• Time: $O(n \log n)$ — four passes with Fenwick tree queries/updates.
• Space: $O(n)$ for the Fenwick trees.
• For $n = 10^6$: runs in seconds.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 733: Ascending Subsequences
 *
 * Sum of all elements in all length-4 ascending subsequences of a_i = 153^i mod 10000019.
 * Uses Fenwick trees for O(n log n) computation.
 */

const int MODP = 1000000007;
const int SEQ_MOD = 10000019;

struct BIT {
    int n;
    vector<long long> tree;
    BIT(int n) : n(n), tree(n + 1, 0) {}
    void update(int i, long long v) {
        for (; i <= n; i += i & -i) tree[i] = (tree[i] + v) % MODP;
    }
    long long query(int i) {
        long long s = 0;
        for (; i > 0; i -= i & -i) s = (s + tree[i]) % MODP;
        return s;
    }
};

int main() {
    int n = 1000000;
    vector<long long> a(n + 1);
    a[1] = 153;
    for (int i = 2; i <= n; i++) a[i] = a[i-1] * 153 % SEQ_MOD;

    // Coordinate compression
    vector<long long> sorted_a(a.begin() + 1, a.end());
    sort(sorted_a.begin(), sorted_a.end());
    sorted_a.erase(unique(sorted_a.begin(), sorted_a.end()), sorted_a.end());
    int sz = sorted_a.size();
    auto compress = [&](long long v) {
        return lower_bound(sorted_a.begin(), sorted_a.end(), v) - sorted_a.begin() + 1;
    };

    vector<BIT> cnt(5, BIT(sz)), sm(5, BIT(sz));
    long long total = 0;

    for (int j = 1; j <= n; j++) {
        int v = compress(a[j]);
        for (int k = 4; k >= 1; k--) {
            long long ck, sk;
            if (k == 1) {
                ck = 1;
                sk = a[j] % MODP;
            } else {
                ck = cnt[k-1].query(v - 1);
                sk = (sm[k-1].query(v - 1) + a[j] % MODP * ck) % MODP;
            }
            cnt[k].update(v, ck);
            sm[k].update(v, sk);
            if (k == 4) total = (total + sk) % MODP;
        }
    }

    printf("%lld\n", total);
    return 0;
}

"""
Problem 733: Ascending Subsequences

Sum of all elements in all ascending subsequences of length 4.
Uses Fenwick trees for efficient prefix sum queries.
"""

MOD = 10**9 + 7
SEQ_MOD = 10_000_019

class BIT:
    """Fenwick tree for prefix sum queries and point updates."""
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] = (self.tree[i] + delta) % MOD
            i += i & (-i)

    def query(self, i):
        s = 0
        while i > 0:
            s = (s + self.tree[i]) % MOD
            i -= i & (-i)
        return s

def solve(n):
    # Generate sequence
    a = [0] * (n + 1)
    a[1] = 153 % SEQ_MOD
    for i in range(2, n + 1):
        a[i] = (a[i-1] * 153) % SEQ_MOD

    # Coordinate compression
    vals = sorted(set(a[1:n+1]))
    compress = {v: i+1 for i, v in enumerate(vals)}
    sz = len(vals)

    # Fenwick trees for counts and sums at each length k=1..4
    cnt = [BIT(sz) for _ in range(5)]   # cnt[k]
    sml = [BIT(sz) for _ in range(5)]   # sum[k]

    total = 0

    for j in range(1, n + 1):
        v = compress[a[j]]
        for k in range(4, 0, -1):
            if k == 1:
                ck = 1
                sk = a[j] % MOD
            else:
                ck = cnt[k-1].query(v - 1)
                sk = (sml[k-1].query(v - 1) + a[j] * ck) % MOD
            cnt[k].update(v, ck)
            sml[k].update(v, sk)
            if k == 4:
                total = (total + sk) % MOD

    return total

# Verify small case
s6 = solve(6)
print(f"S(6) = {s6}")  # Expected: 94513710

s100 = solve(100)
print(f"S(100) = {s100}")  # Expected: 4465488724217 mod MOD

# Full answer
# s_1m = solve(1000000)
# print(f"S(10^6) mod 10^9+7 = {s_1m}")