Extreme Extension
题意翻译
对于一个数列,定义一次操作为选择数列中任何一个元素 $a_i$ ,将这个位置替换成两个**正整数** $x,y$ 满足 $x+y=a_i$
定义一个数列的极端值为将这个数列变成**不降**数列的最小操作次数
给定一个长度为 $n$ 的数列 $a$ ( $1\leq a_i\leq 10^5$ ),让你求它的所有非空子段的极端值之和,对 $\text{998244353}$ 取模
一个测试点中有多组数据,保证所有数据 $n$ 的规模总和不超过 $10^5$
题目描述
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.
输入输出格式
输入格式
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 $ .
输出格式
For each test case, print a single integer — the sum of extreme values of all subarrays of $ a $ modulo $ 998\,244\,353 $ .
输入输出样例
输入样例 #1
4
3
5 4 3
4
3 2 1 4
1
69
8
7264 40515 28226 92776 35285 21709 75124 48163
输出样例 #1
5
9
0
117
说明
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 $ .