#P12471. [2025年福建省队集训]沙湾

    ID: 11634 传统题 1000ms 256MiB 尝试: 7 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-计数 DP滚动数组贡献法重复元素除重阶乘逆元预处理

[2025年福建省队集训]沙湾

题目描述

你手上有 n+mn+m 个石子,有 nn 个普通的石子和 mm 个特殊的石子。

这 n+mn+m 个石子共有 c+1c+1 种颜色,其中 mm 个特殊的石子的颜色为 c+1c+1,其余石子的颜色为 1∼c1\sim c 中的一种。

已知第 ii 种颜色的石子有 aia_i 个,保证 ∑i=1cai=n\sum_{i=1}^c a_i=n。

你将这些石子摆成一行,你决定观察你摆的石子的美观度。

为了方便观察,美观度由最左边和最右边的石子决定,具体如下:

  • 找到最左边的特殊的石子,记其为从左到右的第 xx 个石子。

  • 考虑最右边的石子,如果是普通石子,则找到这个石子左边第一个颜色不同的石子(可以是特殊石子),记其右边的石子数为 yy。

例如,有 55 个石子,从左到右颜色依次为 2,3,3,1,12,3,3,1,1,其中颜色 1,21,2 为普通石子,颜色 33 为特殊石子。

最左边的特殊石子是从左到右第 22 个石子,所以 x=2x=2。

最右边的石子颜色是 11,是一个普通石子,左边第一个颜色不同的石子是从左到右第 33 个石子,它的右边有 22 个石子,所以 y=2y=2。

序列的美观度定义如下:

  • 如果最右边的石子是特殊的石子,则美观度为 wxw_x。
  • 否则,记最右边的石子颜色为 uu,则美观度为 wx×vu,yw_x\times v_{u,y}。

其中 ww 和 vv 由题目给定。

现在你想知道,所有不同的石子序列,美观度之和是多少?

两个序列不同当且仅当至少有一个位置的石子颜色不同,答案对 998244353998244353 取模。

输入格式

从文件 sand.in 中读入。

第一行 33 个数,表示 n,m,cn,m,c。

第二行 n+1n+1 个数,表示 w1∼wn+1w_1\sim w_{n+1}。

第三行 cc 个数,表示每种颜色的石子个数。

接下来 cc 行,第 ii 行 aia_i 个数,表示 vi,1∼vi,aiv_{i,1}\sim v_{i,a_i}。

输出格式

输出到文件 sand.out 中。

输出一行一个整数,表示所有不同的石子序列的美观度之和对 998244353998244353 取模的结果。

样例

样例输入 1

2 1 1
2 3 4
2
2 3

样例输出 1

16

样例解释 1

共有 33 种可能序列。

{1,1,2}\{1,1,2\},x=3x=3,最右边是特殊石子,美观度为 w3=4w_3=4。

{1,2,1}\{1,2,1\},x=2,y=1x=2,y=1,美观度为 w2×v1,1=3×2=6w_2\times v_{1,1}=3\times 2=6。

{2,1,1}\{2,1,1\},x=1,y=2x=1,y=2,美观度为 w1×v1,2=2×3=6w_1\times v_{1,2}=2\times 3=6。

总和为 4+6+6=164+6+6=16。

样例输入 2

8 2 6
923945407 493986782 501032365 554208540 820758204 352305609 320140120 118497648 467798137 
3 1 1 1 1 1 
297408812 522217066 885036796 
441963214 
132614765 
507229015 
950047419 
634968424 

样例输出 2

734049932

样例 3

见选手目录下的 sand/sand3.in 与 sand/sand3.ans。

这个样例满足测试点 6∼76\sim 7 的约束条件。

样例 4

见选手目录下的 sand/sand4.in 与 sand/sand4.ans。

这个样例满足测试点 8∼108\sim 10 的约束条件。

样例 5

见选手目录下的 sand/sand5.in 与 sand/sand5.ans。

这个样例满足测试点 16∼1716\sim 17 的约束条件。

样例 6

见选手目录下的 sand/sand6.in 与 sand/sand6.ans。

这个样例满足测试点 18∼1918\sim 19 的约束条件。

样例 7

见选手目录下的 sand/sand7.in 与 sand/sand7.ans。

这个样例满足测试点 20∼2220\sim 22 的约束条件。

数据范围

对于 100100% 的数据,1≤c≤n≤2×1051\le c\le n\le 2\times 10^5,1≤m≤301\le m\le 30,ai≥1a_i\ge 1,∑i=1cai=n\sum_{i=1}^c a_i=n,0≤w,v<9982443530\le w,v\lt 998244353。

测试点编号 nn mm 特殊限制
1,21,2 ≤10\le 10 n+m≤10n+m\le 10
33 ≤2×105\le 2\times10^5 =1=1 c=1c=1
4,54,5 ≤2×105\le 2\times 10^5 无
6,76,7 ≤30\le 30 c=1c=1
8,9,108,9,10 ≤200\le 200 无
11,12,13,1411,12,13,14 ≤2000\le 2000
1515 ≤2×105\le 2\times 10^5 保证 vi,j=1,wi=1v_{i,j}=1,w_i=1
16,1716,17 保证 wi=1w_i=1
18,1918,19 保证 vi,j=1v_{i,j}=1
20,21,2220,21,22 =2=2 无
23,24,2523,24,25 ≤30\le 30