题目背景
本题相较于 P9919 扩大了数据范围。
题目描述
对于一个右部点为 m 个的二分图 G,定义它的权值 w(G) 如下:
- 选择一种匹配方案,标记第一个已匹配的右部点。如果不存在这样的点,那么标记第一个未匹配的右部点。
- 每次随机选择一个 1,2,⋯,m 的排列,当未匹配的右部点与被标记的点 按标号顺序作为一个子段出现在排列中时 停止操作。
- w(G) 为在所有匹配方案中操作次数期望的 最小值。
将这个二分图 G 定义为 k 合法 的,当且仅当:
- 所有左部点的度数在 k∼2 之间。
- 没有任意两个左部点,与其相邻的点组成的集合相同。
定义 f(k,x) 为所有右部点 x 个,左部点不进行区分的 k 合法二分图 G 的 w(G) 之和。
给定 n,k,a0∼n,求 i∑naif(k,i)mod998244353。
输入格式
一行两个正整数,分别表示 n,k。
第二行 n+1 个非负整数,分别表示 a0∼n。
输出格式
一行一个非负整数,表示答案。
提示
约定一个左部点连接了编号为 x,y 的右部点表示为 (x,y)。
【样例 1 解释】
对于 n=0,1,答案显然为 1,2。
对于 n=2,可能的二分图为(用每个左部点的邻接点组成的元组表示):
()
(1),(2),(1,2)
{(1),(2)},{(1,2),(2)},{(1,2),(1)},{(1,2),(1),(2)}
期望相同的二分图被分为一组。答案为 12+12×3+22×4=12,输出 1×1+1×2+1×12=15。
【样例 2 解释】
对于 n=0,1,2,答案为 1,1,4。
对于 n=3,可能的二分图为(用每个左部点的邻接点组成的元组表示):
()
(1,2),(1,3),(2,3)
{(1,2),(1,3)},{(1,2),(2,3)},{(1,3),(2,3)}
{(1,2),(2,3),(1,3)}
答案为 16+16×3+26×3+66=34。
【数据范围】
对于 100% 的数据,0≤n≤105,1≤k≤2,0≤ai<998244353。