No.2950 Max Min Product
レベル :
/ AI推定難易度 : 2000
/ 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 28
作問者 :
nouka28
/ テスター :
rotti_coder
t9unkubj
タグ : / 解いたユーザー数 28
作問者 :
nouka28
/ テスター :
rotti_coder
t9unkubj
問題文最終更新日: 2024-10-18 06:39:00
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
Problem Statement
You are given a sequence of positive integers $A=(A_1,A_2,\dots,A_N)$ of length $N$. Find the following value modulo $998244353$.
$\displaystyle \sum_{l=1}^{N}\sum_{r=l}^{N}{\max(A_l,A_{l+1},\dots,A_r)\times \min(A_l,A_{l+1},\dots,A_r)}$
Constraints
- $1\leq N\leq 2\times 10^5$
- $1\leq A_i\leq 10^9$
- All input values are integers.
Input
The input is given from Standard Input in the following format.$N$ $A_1$ $A_2$ $\dots$ $A_N$
Output
Output the answer.
Sample
Sample 1
Input
4 2 1 3 2
Output
38
$A$ has the following $10$ contiguous subarrays.
- $\max(A_1)\times\min(A_1)=2\times 2=4$
- $\max(A_2)\times\min(A_2)=1\times 1=1$
- $\max(A_3)\times\min(A_3)=3\times 3=9$
- $\max(A_4)\times\min(A_4)=2\times 2=4$
- $\max(A_1,A_2)\times\min(A_1,A_2)=2\times 1=2$
- $\max(A_2,A_3)\times\min(A_2,A_3)=3\times 1=3$
- $\max(A_3,A_4)\times\min(A_3,A_4)=3\times 2=6$
- $\max(A_1,A_2,A_3)\times\min(A_1,A_2,A_3)=3\times 1=3$
- $\max(A_2,A_3,A_4)\times\min(A_2,A_3,A_4)=3\times 1=3$
- $\max(A_1,A_2,A_3,A_4)\times\min(A_1,A_2,A_3,A_4)=3\times 1=3$
Since $\displaystyle \sum_{l=1}^{4}\sum_{r=l}^{4}{\max(A_l,A_{l+1},\dots,A_r)\times \min(A_l,A_{l+1},\dots,A_r)}=4+1+9+4+2+3+6+3+3+3=38$, the answer is $38$, which is the remainder when $38$ is divided by $998244353$.
Sample 2
Input
1 1
Output
1
Sample 3
Input
10 283946572 281630273 475961938 982637405 293709717 192730741 789163287 987382638 182630462 567839465
Output
771208723
Find the remainder when divided by $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。