#j. LEQ

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l

Type: RemoteJudge

2000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面翻译

给定一个长度为 $N$ 的序列 $A=(A_1,A_2,..., A_N)$ 。

求出子序列的总数，使得对于任意的子序列 $A'=(A'_1,A'_2,...,A'_k)$ ，满足 $A'_1 \le A'_k$ 。

答案对 $998244353$ 取模。

题目描述

長さ $N$ の整数列 $A\ =\ (A_1,\ A_2,\ \dots,\ A_N)$ が与えられます。

$A$ の連続するとは限らない、長さが $2$ 以上である部分列 $A'=(A'_1,A'_2,\ldots,A'_k)$ のうち以下の条件を満たすものの個数を求めてください。

$A'_1\ \leq\ A'_k$

なお、この値は非常に大きくなることがあるため、 $998244353$ で割ったあまりを出力してください。

ただし、 $2$ つの部分列は、列として同じであっても、取り出す添字が異なる場合は区別されます。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

$A$ の連続するとは限らない、長さが $2$ 以上である部分列のうち問題文中の条件を満たすものの個数を、 $998244353$ で割ったあまりを出力せよ。

样例 #1

样例输入 #1

3
1 2 1

样例输出 #1

样例 #2

样例输入 #2

3
1 2 2

样例输出 #2

样例 #3

样例输入 #3

3
3 2 1

样例输出 #3

样例 #4

样例输入 #4

10
198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501

样例输出 #4

提示

制約

$2\ \leq\ N\ \leq\ 3\ \times\ 10^5$
$1\ \leq\ A_i\ \leq\ 10^9$
入力はすべて整数

Sample Explanation 1

$A=(1,2,1)$ の連続するとは限らない、長さが $2$ 以上である部分列は $(1,2)$ , $(1,1)$ , $(2,1)$ , $(1,2,1)$ の $4$ 通りあります。そのうち問題文中の条件を満たすものは、 $(1,2)$ , $(1,1)$ , $(1,2,1)$ の $3$ 通りです。

Sample Explanation 2

列として同じであっても、取り出す添字が異なる場合 $2$ つの部分列は区別されることに注意してください。この入出力例において、問題文中の条件を満たすような部分列は $(1,2)$ , $(1,2)$ , $(2,2)$ , $(1,2,2)$ の $4$ 通りです。

Sample Explanation 3

問題文中の条件を満たすような部分列が存在しない場合もあります。

北辰OI提高组第2周序列问题课后练习题👍

Not Attended

Status: Done
Rule: IOI
Problem: 44
Start at: 2024-1-7 16:00
End at: 2024-2-18 8:00
Duration: 1000 hour(s)
Host: yuyongchao
Partic.: 15

#j. LEQ

LEQ

题面翻译

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

样例 #3

样例输入 #3

样例输出 #3

样例 #4

样例输入 #4

样例输出 #4

提示

制約

Sample Explanation 1

Sample Explanation 2

Sample Explanation 3

北辰OI提高组第2周序列问题课后练习题👍

Status

Development

Support

#j. LEQ

LEQ

题面翻译

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

样例 #3

样例输入 #3

样例输出 #3

样例 #4

样例输入 #4

样例输出 #4

提示

制約

Sample Explanation 1

Sample Explanation 2

Sample Explanation 3

北辰OI提高组第2周序列问题课后练习题👍

Status

Development

Support

Don't have an account?

SIGN IN