#P17801. [CXOI2026] 大潘小潘向前 p
[CXOI2026] 大潘小潘向前 p
题目描述
:::info[原题面] 大潘是一名非常喜欢说 p 话的选手。作为 p 话队队长,大潘每天都会说很多句 p 话。作为大潘的忠实粉丝,小潘连续研究了了大潘 天说的 p 话,她发现在这 天里,大潘第 天说的 p 话可以用一个二元组 来表示。小潘作为一名美丽且善于观察的队娘,她发现这 句 p 话还可以表示为一个长度为 的整数序列 ,序列 同时满足下面的三个条件:
- 。
- 恰好有 个不同的位置 满足 且 。
- 对所有满足 的位置 ,都有 。
其中 是小潘选定的两个 p 话参数。
但是由于大潘说 p 话的能力不断提升,小潘很快发现自己原来选择的参数 已经不足以描述大潘 p 话的鲜活程度了,于是她决定对 都计算有多少个合法的 序列。因为大潘实在是太过于 p 了,小潘发现她的大脑难以存储这么巨大的数字,因此你只需要帮助她算出合法的序列 数量对大质数 取模后的结果即可。 :::
Luminescent 给了你三个整数 和 个限制二元组 。
Loyalty 需要统计长度为 的整数序列 的数量。序列 必须满足:
- 每个元素都在范围内:。
- 序列中恰好有 个下降位置,即恰好有 个 满足 且 。
- 对每个限制 ,都要求 。
Loyalty 想要对每个 ,分别计算满足条件的序列 的数量,并将答案对 取模后输出。你现在需要帮助 Loyalty 解决这个问题。
输入格式
本题有多组测试数据。第一行一个整数 表示共有 组测试数据。
对于每组数据:
- 第一行三个整数 。
- 然后 行一行两个整数 。
输出格式
对于每组数据:
- 一行 个由一个空格分隔的整数,第 个整数表示 时序列 的数量对 取模后的结果。
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 捆绑测试。
对于 的分数满足 。
对于 的分数满足 。
对于另外 的分数满足 。
对于另外 的分数满足 。
对于另外 的分数满足 。
对于全部的分数满足 $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$。