题目详情题解（0）讨论（0）提交记录（0）

AT_awtf2025_b.Movies

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Maroon 的暑假有 NN 天。在假期中有 MM 种电影被排期放映，第 ii 种电影将在第 LiL_i 天到第 RiR_i 天被放映。

对于一个所有电影的子集 ss，我们定义 f(s)f(s)：

  • f(s)f(s) 是只能看 ss 中的电影，且每天只能看一场电影的前提下，Maroon 在假期中最多观看的电影种类数。重复观看同种电影只计一次。

所有电影的子集 ss 有 2M2^M 个，你要求出所有 ss 的 f(s)f(s) 之和，对 998244353998244353 取模。

输入格式

第一行两个整数 N,MN,M。

接下来 MM 行，每行两个整数 Li,RiL_i,R_i。

输出格式

一行一个整数表示答案。

输入输出样例

  • 输入#1

    2 3
1 1
2 2
1 2

    输出#1

    11

  • 输入#2

    3 3
1 1
2 2
3 3

    输出#2

    12

  • 输入#3

    4 10
3 3
2 4
2 3
4 4
3 4
1 3
1 1
2 2
1 2
1 4

    输出#3

    3796

  • 输入#4

    7 20
1 3
4 5
3 3
3 5
1 4
4 7
2 3
1 7
6 7
4 6
2 4
6 6
3 6
2 5
7 7
3 4
2 2
5 5
2 6
1 2

    输出#4

    7113137

说明/提示

数据范围

  • 1≤N≤1001\le N\le 100
  • 1≤M≤N×(N+1)/21\le M\le N\times(N+1)/2
  • 1≤Li≤Ri≤N1\le L_i\le R_i\le N
  • (Li,Ri)≠(Lj,Rj)(i≠j)(L_i,R_i)\ne (L_j,R_j)(i\ne j)
  • 所有输入均为整数。

样例 1 解释

s={1,2,3}s=\{1,2,3\} 有 f(s)=2f(s)=2，其他的 ss 均有 f(s)=∣s∣f(s)=\vert s\vert。f(s)f(s) 的和为 1111。

输入解题思路，AI测评打分。不知道怎么写?

首页