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

AT_abc262_h.[ABC262Ex] Max Limited Sequence

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

题目大意

求满足以下条件的长度为 NN 的序列 A=(A1,A2,⋯AN)A=(A_1,A_2,\cdots A_N) 有多少种：

  • ∀i∈[1,N],0≤Ai≤M\forall i \in[1,N],0\leq A_i\leq M
  • ∀i∈[1,Q],max⁡Li≤j≤RiAj=Xi\forall i \in[1,Q],\max \limits_{L_i\leq j\leq R_i}A_j=X_i

输入格式

第一行输入 33 个正整数 N,M,QN,M,Q

后面 QQ 行每行 33 个正整数表示 Li,Ri,XiL_i,R_i,X_i

1≤N≤2×1051\leq N\leq 2\times 10^5

1≤M<9982443531\leq M<998244353

1≤Q≤2×1051\leq Q\leq 2\times 10^5

∀i∈[1,Q],1≤Li≤Ri≤N,1≤Xi≤M\forall i \in [1,Q],1\leq L_i\leq R_i\leq N,1\leq X_i\leq M

输出格式

输出满足条件的序列数，对 998244353998244353 取模。

输入输出样例

  • 输入#1

    3 3 2
1 2 2
2 3 3

    输出#1

    5

  • 输入#2

    1 1 1
1 1 1

    输出#2

    1

  • 输入#3

    6 40000000 3
1 4 30000000
2 6 20000000
3 5 10000000

    输出#3

    135282163

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

首页