33OJ
登录 注册

#P17801. [CXOI2026] 大潘小潘向前 p

    ID: 20387 远端评测题 2000ms 512MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>动态规划 DP区间 DP组合数学

[CXOI2026] 大潘小潘向前 p

题目描述

:::info[原题面] 大潘是一名非常喜欢说 p 话的选手。作为 p 话队队长,大潘每天都会说很多句 p 话。作为大潘的忠实粉丝,小潘连续研究了了大潘 mm 天说的 p 话,她发现在这 mm 天里,大潘第 ii 天说的 p 话可以用一个二元组 (xi,yi)(x_i,y_i) 来表示。小潘作为一名美丽且善于观察的队娘,她发现这 mm 句 p 话还可以表示为一个长度为 nn 的整数序列 aa,序列 aa 同时满足下面的三个条件:

  • ∀i∈[1,n]∩N+,1≤ai≤V\forall i\in[1,n]\cap\mathbb N_+,1\le a_i\le V。
  • 恰好有 k−1k-1 个不同的位置 ii 满足 1≤i<n1\le i<n 且 ai>ai+1a_i>a_{i+1}。
  • 对所有满足 1≤i≤m1\le i\le m 的位置 ii,都有 axi≤yia_{x_i}\le y_i。

其中 k,Vk,V 是小潘选定的两个 p 话参数。

但是由于大潘说 p 话的能力不断提升,小潘很快发现自己原来选择的参数 k,Vk,V 已经不足以描述大潘 p 话的鲜活程度了,于是她决定对 k=1,2,3,…nk=1,2,3,\ldots n 都计算有多少个合法的 aa 序列。因为大潘实在是太过于 p 了,小潘发现她的大脑难以存储这么巨大的数字,因此你只需要帮助她算出合法的序列 aa 数量对大质数 998244353998244353 取模后的结果即可。 :::

Luminescent 给了你三个整数 n,m,Vn,m,V 和 mm 个限制二元组 (xi,yi)(x_i,y_i)。

Loyalty 需要统计长度为 nn 的整数序列 aa 的数量。序列 aa 必须满足:

  1. 每个元素都在范围内:1≤ai≤V1 \le a_i \le V。
  2. 序列中恰好有 k−1k-1 个下降位置,即恰好有 k−1k-1 个 ii 满足 1≤i<n1 \le i < n 且 ai>ai+1a_i > a_{i+1}。
  3. 对每个限制 (xi,yi)(x_i,y_i),都要求 axi≤yia_{x_i} \le y_i。

Loyalty 想要对每个 k=1,2,…,nk=1,2,\ldots,n,分别计算满足条件的序列 aa 的数量,并将答案对 998244353998244353 取模后输出。你现在需要帮助 Loyalty 解决这个问题。

输入格式

本题有多组测试数据。第一行一个整数 TT 表示共有 TT 组测试数据。

对于每组数据:

  • 第一行三个整数 n,m,Vn,m,V。
  • 然后 mm 行一行两个整数 xi,yix_i,y_i。

输出格式

对于每组数据:

  • 一行 nn 个由一个空格分隔的整数,第 ii 个整数表示 k=ik=i 时序列 aa 的数量对 998244353998244353 取模后的结果。
3
5 3 4
2 3
4 2
5 3
4 2 3
1 2
3 2
6 3 3
2 2
4 1
6 2
11 129 129 19 0
9 24 3 0
3 33 51 21 0 0

提示

本题使用 Subtask 捆绑测试。

对于 10%10\% 的分数满足 n,V≤8n,V\le 8。

对于 35%35\% 的分数满足 n≤80n\le 80。

对于另外 10%10\% 的分数满足 V≤500V\le 500。

对于另外 15%15\% 的分数满足 m=0m=0。

对于另外 15%15\% 的分数满足 m=n,xi=i,y1≥y2≥…≥ynm=n,x_i=i,y_1\ge y_2\ge \ldots\ge y_n。

对于全部的分数满足 $1\le T\le 5,1\le x_i,m\le n\le 500,1\le y_i\le V\le 10^9,\sum n\le 10^3,x_1<x_2<\ldots<x_m$。