#P18905. [2026多校联测]cubepack

[2026多校联测]cubepack

题目描述

小 M 有 nn 种正方体。第 ii 种正方体的体积为 viv_i,数量为 cic_i。

此外,有的正方体有至多一个依附正方体 hih_i:如果小 M 将正方体 hih_i 禁用,那么正方体 ii 也会被禁用;hi=0h_i=0 表示第 ii 种正方体没有依附的正方体。保证这种依附关系不会形成环。

由于有的正方体过于难看,小 M 有时会禁用一种正方体。被禁用的正方体不能被装进背包。

现在小 M 想知道,如果背包容量为 ww、禁用的正方体为 kk,想要恰好填满这个背包,共有多少种方案。两个方案不同,当且仅当存在某个 ii,使得两种方案中第 ii 种正方体被装入的数量不同。

答案对 107+710^7+7 取模。

输入格式

第一行三个整数 n,w,kn,w,k,依次表示正方体的种数、背包容量、被禁用的正方体编号。

接下来 nn 行,第 ii 行三个整数 vi,ci,hiv_i,c_i,h_i,依次表示第 ii 种正方体的体积、数量、依附的正方体编号(hi=0h_i=0 表示没有依附)。

输出格式

一行一个整数,表示恰好填满背包的方案数对 107+710^7+7 取模的结果。

样例 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:禁用第 33 种后,只剩下第 1,21,2 种可用,需要 2x+4y=62x+4y=6,有 (x,y)=(3,0)(x,y)=(3,0) 与 (1,1)(1,1) 两种方案,答案为 22。
  • 样例 2:第 33 种依附于第 22 种,禁用第 22 种会连带禁用第 33 种;剩下第 1,41,4 种,需要 2x+3y=62x+3y=6,有两种方案,答案为 22。
  • 样例 3:禁用第 33 种后,第 1,21,2 种的数量都足够大,需要 2x+3y=102x+3y=10,有 (5,0)(5,0) 与 (2,2)(2,2) 两种方案,答案为 22。

子任务

测试点编号 约束 分值
1 n≤8n\le8,w≤1000w\le1000,ci≤20c_i\le20,且所有 hi=0h_i=0 20
2-3 ci=1c_i=1,且所有 hi=0h_i=0
4-5 所有 hi=0h_i=0
6-10 无特殊限制 40

对于 100%100\% 的数据,1≤n≤1001\le n\le100,1≤w≤5×1041\le w\le5\times10^4,1≤vi≤1091\le v_i\le10^9,1≤ci≤1091\le c_i\le10^9,0≤hi≤n0\le h_i\le n,1≤k≤n1\le k\le n,且依附关系不形成环。