#P18552. Exchanging Kubic 2
Exchanging Kubic 2
Exchanging Kubic 2
小青鱼正在与 Kubic 教授进行一项社会实验。实验中有 n 个人,初始位置分别为 a_1,a_2,…,a_n。你必须恰好进行 n 次操作,每个人只能被选择一次。
每次操作选择一个人,其他所有人同时向这个被选中的人移动一步。具体地,选择第 i 个人时,对每个 j≠i,以本次操作开始时的位置进行比较:
- 若 a_i>a_j,则 a_j←a_j+1;
- 若 a_i<a_j,则 a_j←a_j−1;
- 若 a_i=a_j,则 a_j 保持不变。
被选中的人本次不移动。已经被选择过的人以后仍会按上述规则移动,只是不能再次成为被选中的人。
定义数组 a=(a_1,…,a_n) 的价值:安排全部 n 次操作的顺序,使操作结束后距离最远的两个人之间的距离尽可能小;这个最小距离就是数组的价值。n=1 时该距离为0。
现在给定 n 个集合 S_1,S_2,…,S_n。数组 a 合法当且仅当同时满足:
- 对所有1≤i<n,有 a_i≤a_{i+1};
- 对所有1≤i≤n,有 a_i∈S_i。
请计算所有合法数组的价值之和,答案对998244353取模。不同合法数组各计算一次;操作顺序只用于确定一个数组的最小价值,不作为求和中的不同方案。若没有合法数组,和为0。
输入格式
第一行一个整数 n(1≤n≤400)。
接下来 n 行依次描述 S_i。每行先给出整数 |S_i|(0≤|S_i|≤801),随后给出 |S_i| 个互不相同的整数,均在[0,800]内,表示集合的元素。
集合元素不保证按大小排序。集合可以为空。输入仅包含这一组数据。
输出格式
输出一行一个整数,表示所有合法数组价值之和对998244353取模的结果。
原样例1
5
3 1 2 3
1 2
0
4 0 2 3 4
2 2 3
0
原样例2
5
4 1 2 3 7
4 5 7 8 9
4 2 3 6 9
5 0 1 4 7 9
8 0 1 2 3 6 7 8 9
16