QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 512 MB Total points: 100
[+7]

# 9611. 木桶效应

Statistics

小 D 有 n 个木桶,每个木桶由 m 块类型互不相同的木板构成。对于一个木桶,如果它的木板长度为 a1,a2,...,am,那么这个木桶所能盛放的液体体积为 min

小 D 的 n 个木桶很神奇,它们所能造成的收益并不简单的是每个木桶的液体体积之和,而是每个木桶的液体体积之积。也就是说,对于这 n 个木桶,如果第 i 个木桶的第 j 块木板的高度为 p_{j,i},那么这些木桶造成的收益为 \prod_{i=1}^n (\min_{j=1}^m p_{j,i})

小 D 已经从木材店买到了一些木板,但是,木材店的木板数量是很有限的。具体来说,对于这 m 种木板,每种木板小 D 恰好有 1\sim n 长度的木板各一个。小 D 现在已经放好了 q 条木板,但还没有想好怎么放置这些木板,所以,他希望你能求出来对于所有合法的放置木板的方案对应的收益之和。由于这个数可能很大,所以他只需要你输出对 998244353 取模的结果。

形式化题意

m 个长度为 n 的排列,其中共有 q 个位置的值已经确定,其余位置未确定。求所有本质不同的排列组对应的 \prod_{i=1}^n (\min_{j=1}^m p_{j,i}) 之和。对 998244353 取模。两组排列 P,Q 本质不同,当且仅当存在 i,j 使得 P_{i,j} \neq Q_{i,j}。保证至少存在一种合法方案。

输入格式

第一行三个数 n,m,q,含义见题目描述。

接下来 q 行,每行三个数 x,y,w,表示要求 p_{x,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\leq n\leq 50,1\leq m < 998244353,0\leq q\leq 10,1\leq x\leq m,1\leq y,w\leq n

  • Subtask 1(4pts):n\leq 5,m\leq 3,q\leq 5
  • Subtask 2(8pts):n\leq 7,m\leq 3,q\leq 5
  • Subtask 3(8pts):m\leq 2,q=0
  • Subtask 4(12pts):q=0
  • Subtask 5(16pts):n\leq 20,q\leq 5
  • Subtask 6(12pts):q\leq 5
  • Subtask 7(20pts):q\leq 7
  • Subtask 8(12pts):q\leq 9
  • Subtask 9(8pts):无特殊限制。

时间限制:5s

空间限制:512MB