#1870. 木桶效应
木桶效应
木桶效应
题目描述
标题: 木桶效应 - Problem - QOJ.ac
#9611. 木桶效应
The problem was used in the following contests:
小 D 有 n 个木桶,每个木桶由 m 块类型互不相同的木板构成。对于一个木桶,如果它的木板长度为 a1,a2,...,am,那么这个木桶所能盛放的液体体积为 mini=1mai。
小 D 的 n 个木桶很神奇,它们所能造成的收益并不简单的是每个木桶的液体体积之和,而是每个木桶的液体体积之积。也就是说,对于这 n 个木桶,如果第 i 个木桶的第 j 块木板的高度为 pj,i,那么这些木桶造成的收益为 ∏i=1n(minj=1mpj,i)。
小 D 已经从木材店买到了一些木板,但是,木材店的木板数量是很有限的。具体来说,对于这 m 种木板,每种木板小 D 恰好有 1∼n 长度的木板各一个。小 D 现在已经放好了 q 条木板,但还没有想好怎么放置这些木板,所以,他希望你能求出来对于所有合法的放置木板的方案对应的收益之和。由于这个数可能很大,所以他只需要你输出对 998244353 取模的结果。
形式化题意
有 m 个长度为 n 的排列,其中共有 q 个位置的值已经确定,其余位置未确定。求所有本质不同的排列组对应的 ∏i=1n(minj=1mpj,i) 之和。对 998244353 取模。两组排列 P,Q 本质不同,当且仅当存在 i,j 使得 Pi,j≠Qi,j。保证至少存在一种合法方案。
输入格式
第一行三个数 n,m,q,含义见题目描述。
接下来 q 行,每行三个数 x,y,w,表示要求 px,y=w。
输出格式
一行一个数,表示所有方案的收益之和对 998244353 取模的结果。
样例组
样例 1 输入
2 2 0
样例 1 输出
6
样例 2 输入
3 2 1
1 1 1
样例 2 输出
38
样例 3 输入
50 50 5
6 18 17
10 2 14
43 12 40
11 50 37
45 23 4
样例 3 输出
830538815
数据范围
本题采用捆绑测试。
对于所有的数据,满足 1≤n≤50,1≤m<998244353,0≤q≤10,1≤x≤m,1≤y,w≤n。
- Subtask 1(4pts):n≤5,m≤3,q≤5。
- Subtask 2(8pts):n≤7,m≤3,q≤5。
- Subtask 3(8pts):m≤2,q=0。
- Subtask 4(12pts):q=0。
- Subtask 5(16pts):n≤20,q≤5。
- Subtask 6(12pts):q≤5。
- Subtask 7(20pts):q≤7。
- Subtask 8(12pts):q≤9。
- Subtask 9(8pts):无特殊限制。
时间限制:5s
空间限制:512MB
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
2 2 0
6
样例 2
3 2 1
1 1 1
38