| 题目名称 | 3911. Sum of k_mex |
|---|---|
| 输入输出 | k_mex.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 op_组撒头屯
于2023-09-02加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：1， 通过率：100% | ||||
 op_组撒头屯 |
100 | 0.517 s | 16.71 MiB | C++ |
| 本题关联比赛 | |||
| 2023级模拟测试1 | |||
| 关于 Sum of k_mex 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
op_组撒头屯
2023-09-06 18:33
2楼
| ||||
|
op_组撒头屯
2023-09-06 18:31
1楼
| ||||
【题目描述】
定义一个序列的 $\mathrm{k\_mex}$ 表示不小于 $k$ 且未出现于序列中的最小自然数。
给定一个 $n$ 阶排列 $p$，你需要求出：
$$\sum_{k=1}^{n}{\sum_{1 \le l \le r \le n}{\mathrm{k\_mex}(p_{l \sim r})}}$$
答案对 $998244353$ 取模。
【输入格式】
第一行一个正整数 $n$。
第二行 $n$ 个正整数表示排列 $p$。
【输出格式】
一个整数表示答案。
【样例输入1】
2 1 2
【样例输出1】
14
【样例输入2】
5 1 3 2 4 5
【样例输出2】
291
【数据规模与约定】
对于前 $20\%$ 的数据，保证 $1 \le n \le 100$。
对于前 $40\%$ 的数据，保证 $1 \le n \le 1000$。
对于 $100\%$ 的数据，保证 $1 \le n \le 10^5$。
【来源】
$rsr$