#P18905. [2026多校联测]cubepack
[2026多校联测]cubepack
题目描述
小 M 有 种正方体。第 种正方体的体积为 ,数量为 。
此外,有的正方体有至多一个依附正方体 :如果小 M 将正方体 禁用,那么正方体 也会被禁用; 表示第 种正方体没有依附的正方体。保证这种依附关系不会形成环。
由于有的正方体过于难看,小 M 有时会禁用一种正方体。被禁用的正方体不能被装进背包。
现在小 M 想知道,如果背包容量为 、禁用的正方体为 ,想要恰好填满这个背包,共有多少种方案。两个方案不同,当且仅当存在某个 ,使得两种方案中第 种正方体被装入的数量不同。
答案对 取模。
输入格式
第一行三个整数 ,依次表示正方体的种数、背包容量、被禁用的正方体编号。
接下来 行,第 行三个整数 ,依次表示第 种正方体的体积、数量、依附的正方体编号( 表示没有依附)。
输出格式
一行一个整数,表示恰好填满背包的方案数对 取模的结果。
样例 1
3 6 3
2 3 0
4 1 0
3 1 0
2
样例 2
4 6 2
2 3 0
4 1 0
1 5 2
3 2 0
2
样例 3
3 10 3
2 1000000000 0
3 1000000000 0
1 1000000000 0
2
样例解释
- 样例 1:禁用第 种后,只剩下第 种可用,需要 ,有 与 两种方案,答案为 。
- 样例 2:第 种依附于第 种,禁用第 种会连带禁用第 种;剩下第 种,需要 ,有两种方案,答案为 。
- 样例 3:禁用第 种后,第 种的数量都足够大,需要 ,有 与 两种方案,答案为 。
子任务
| 测试点编号 | 约束 | 分值 |
|---|---|---|
| 1 | ,,,且所有 | 20 |
| 2-3 | ,且所有 | |
| 4-5 | 所有 | |
| 6-10 | 无特殊限制 | 40 |
对于 的数据,,,,,,,且依附关系不形成环。