{"problem":{"name":"「RiOI-03」A Journey to the Moonlight（加强版）","description":{"content":"对于一个右部点为 $m$ 个的二分图 $G$，定义它的权值 $w(G)$ 如下： - 选择一种匹配方案，标记第一个已匹配的右部点。如果不存在这样的点，那么标记第一个未匹配的右部点。 - 每次随机选择一个 $1,2,\\cdots,m$ 的排列，当未匹配的右部点与被标记的点 **按标号顺序作为一个子段出现在排列中时** 停止操作。 - $w(G)$ 为在所有匹配方案中操作次数期望的 **最小值**。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10286"},"statements":[{"statement_type":"Markdown","content":"对于一个右部点为 $m$ 个的二分图 $G$，定义它的权值 $w(G)$ 如下：\n\n- 选择一种匹配方案，标记第一个已匹配的右部点。如果不存在这样的点，那么标记第一个未匹配的右部点。\n- 每次随机选择一个 $1,2,\\cdots,m$ 的排列，当未匹配的右部点与被标记的点 **按标号顺序作为一个子段出现在排列中时** 停止操作。\n- $w(G)$ 为在所有匹配方案中操作次数期望的 **最小值**。\n\n将这个二分图 $G$ 定义为 **$k$ 合法** 的，当且仅当：\n\n- 所有左部点的度数在 $k\\sim \\color{red}2$ 之间。\n- 没有任意两个左部点，与其相邻的点组成的集合相同。\n\n定义 $f(k,x)$ 为所有右部点 $x$ 个，左部点不进行区分的 $k$ 合法二分图 $G$ 的 $w(G)$ 之和。\n\n给定 $n,k,a_{0\\sim n}$，求 $\\sum\\limits^n_ia_if(k,i) \\bmod998244353$。\n\n## Input\n\n一行两个正整数，分别表示 $n,k$。\n\n第二行 $n+1$ 个非负整数，分别表示 $a_{0\\sim n}$。\n\n## Output\n\n一行一个非负整数，表示答案。\n\n[samples]\n\n## Background\n\n本题相较于 [P9919](/problem/P9919) 扩大了数据范围。\n\n## Note\n\n约定一个左部点连接了编号为 $x,y$ 的右部点表示为 $(x,y)$。\n\n#### 【样例 1 解释】\n\n对于 $n=0,1$，答案显然为 $1,2$。\n\n对于 $n=2$，可能的二分图为（用每个左部点的邻接点组成的元组表示）：\n\n$()$\n\n$(1),(2),(1,2)$\n\n$\\{(1),(2)\\},\\{(1,2),(2)\\},\\{(1,2),(1)\\},\\{(1,2),(1),(2)\\}$\n\n期望相同的二分图被分为一组。答案为 $\\dfrac21+\\dfrac21\\times3+\\dfrac22\\times4=12$，输出 $1\\times1+1\\times2+1\\times12=15$。\n\n#### 【样例 2 解释】\n\n对于 $n=0,1,2$，答案为 $1,1,4$。\n\n对于 $n=3$，可能的二分图为（用每个左部点的邻接点组成的元组表示）：\n\n$()$\n\n$(1,2),(1,3),(2,3)$\n\n$\\{(1,2),(1,3)\\},\\{(1,2),(2,3)\\},\\{(1,3),(2,3)\\}$\n\n$\\{(1,2),(2,3),(1,3)\\}$\n\n答案为 $\\dfrac61+\\dfrac61\\times3+\\dfrac62\\times3+\\dfrac66=34$。\n\n#### 【数据范围】\n\n对于 $100\\%$ 的数据，$0\\le n\\le10^5$，$1\\le k\\le2$，$0\\le a_i<998244353$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10286","tags":["洛谷原创","二分图","生成函数","快速数论变换 NTT"],"sample_group":[["2 1\n1 1 1","15"],["3 2\n1 1 1 1","40"],["12 1\n1 1 4 5 1 4 1 9 1 9 8 1 0","721168027"]],"created_at":"2026-03-03 11:09:25"}}