問題一覧 > 通常問題

No.2950 Max Min Product

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 27
作問者 : nouka28nouka28 / テスター : rotti_coderrotti_coder t9unkubjt9unkubj
2 ProblemId : 10992 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-10-18 06:39:00

問題文

長さ $N$ の正整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられるので以下の値を $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)}$

制約

  • $1\leq N\leq 2\times 10^5$
  • $1\leq A_i\leq 10^9$
  • 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。 
$N$
$A_1$ $A_2$ $\dots$ $A_N$

出力

答えを出力せよ。

サンプル

サンプル1
入力
4
2 1 3 2
出力
38

$A$ の連続部分列は以下の $10$ 通りあります。

  • $\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$

$\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$ なので $38$ を $998244353$ で割った余りの $38$ が答えになります。

サンプル2
入力
1
1
出力
1
サンプル3
入力
10
283946572 281630273 475961938 982637405 293709717 192730741 789163287 987382638 182630462 567839465
出力
771208723

$998244353$ で割った余りを求めてください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。