Extreme Extension (Codeforces 1604E)
Tags: Greedy, number theory

For an array $$$b$$$ of $$$n$$$ integers, the extreme value of this array is the minimum number of times (possibly, zero) the following operation has to be performed to make $$$b$$$ non-decreasing:   Select an index $$$i$$$ such that $$$1 \le i \le |b|$$$, where $$$|b|$$$ is the current length of $$$b$$$.  Replace $$$b_i$$$ with two elements $$$x$$$ and $$$y$$$ such that $$$x$$$ and $$$y$$$ both are positive integers and $$$x + y = b_i$$$.  This way, the array $$$b$$$ changes and the next operation is performed on this modified array. For example, if $$$b = [2, 4, 3]$$$ and index $$$2$$$ gets selected, then the possible arrays after this operation are $$$[2, \underline{1}, \underline{3}, 3]$$$, $$$[2, \underline{2}, \underline{2}, 3]$$$, or $$$[2, \underline{3}, \underline{1}, 3]$$$. And consequently, for this array, this single operation is enough to make it non-decreasing: $$$[2, 4, 3] \rightarrow [2, \underline{2}, \underline{2}, 3]$$$.It's easy to see that every array of positive integers can be made non-decreasing this way.YouKn0wWho has an array $$$a$$$ of $$$n$$$ integers. Help him find the sum of extreme values of all nonempty subarrays of $$$a$$$ modulo $$$998\,244\,353$$$. If a subarray appears in $$$a$$$ multiple times, its extreme value should be counted the number of times it appears.An array $$$d$$$ is a subarray of an array $$$c$$$ if $$$d$$$ can be obtained from $$$c$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10\,000$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$).It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

Output: For each test case, print a single integer  — the sum of extreme values of all subarrays of $$$a$$$ modulo $$$998\,244\,353$$$.

Note: Let $$$f(l, r)$$$ denote the extreme value of $$$[a_l, a_{l+1}, \ldots, a_r]$$$.In the first test case,   $$$f(1, 3) = 3$$$, because YouKn0wWho can perform the following operations on the subarray $$$[5, 4, 3]$$$ (the newly inserted elements are underlined):$$$[5, 4, 3] \rightarrow [\underline{3}, \underline{2}, 4, 3] \rightarrow [3, 2, \underline{2}, \underline{2}, 3] \rightarrow [\underline{1}, \underline{2}, 2, 2, 2, 3]$$$; $$$f(1, 2) = 1$$$, because $$$[5, 4] \rightarrow [\underline{2}, \underline{3}, 4]$$$; $$$f(2, 3) = 1$$$, because $$$[4, 3] \rightarrow [\underline{1}, \underline{3}, 3]$$$; $$$f(1, 1) = f(2, 2) = f(3, 3) = 0$$$, because they are already non-decreasing. So the total sum of extreme values of all subarrays of $$$a = 3 + 1 + 1 + 0 + 0 + 0 = 5$$$.

Sample Inputs:
4
3
5 4 3
4
3 2 1 4
1
69
8
7264 40515 28226 92776 35285 21709 75124 48163

Sample Outputs:
5
9
0
117

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]
mod = 998244353
mask = (1 << 17) - 1

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    dp = []
    for i in range(n - 1, -1, -1):
        ai = a[i]
        ndp = [(ai << 17) + 1]
        last = ai
        for z in dp:
            x = z >> 17
            y = z & mask
            res = (ai + x - 1) // x
            res2 = ai // res
            ans += (res - 1) * y * (i + 1)
            if res2 == last:
                ndp[-1] += y
            else:
                ndp.append((res2 << 17) + y)
                last = res2
        dp = ndp
        ans %= mod
    print(ans)
for _ in range(int(input())):
    solve()

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]
mod = 998244353

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    dp = []
    for i in range(n - 1, -1, -1):
        ai = a[i]
        ndp = [[ai, 1]]
        last = ai
        for (x, y) in dp:
            res = (ai + x - 1) // x
            res2 = ai // res
            ans += (res - 1) * y * (i + 1)
            if res2 == last:
                ndp[-1][1] += y
            else:
                ndp.append([res2, y])
                last = res2
        dp = ndp
        ans %= mod
        if len(dp) >= 2000:
            print(len(dp))
    print(ans)
for _ in range(int(input())):
    solve()

Solution (Python):
from collections import Counter
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))[::-1]
    ans = 0
    mod = 998244353
    max_val = Counter()
    for i in range(n):
        a_i = a[i]
        temp_max_val = Counter()
        for (j, db) in max_val.items():
            if j >= a_i:
                temp_max_val[a_i] += db
            else:
                reszre_oszt = (a_i - 1) // j + 1
                ans += (reszre_oszt - 1) * db * (n - i)
                ans %= mod
                temp = a_i // reszre_oszt
                temp_max_val[temp] += db
        temp_max_val[a_i] += 1
        max_val = temp_max_val
    print(ans)