#1870. 木桶效应

    ID: 1870 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1827来源:qoj.ac数据:公开样例数学

木桶效应

木桶效应

题目描述

标题: 木桶效应 - Problem - QOJ.ac

#9611. 木桶效应

Statistics

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