#P16110. [2026年山东集训一轮]password密码

    ID: 15321 传统题 1500ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3000动态规划字符串数学计数DP

[2026年山东集训一轮]password密码

题目描述

给定 n,mn,m 和一个长度为 n−1n-1 的序列

w1,w2,…,wn−1.w_1,w_2,\ldots,w_{n-1}.

对一个长度为 nn、元素均在 [1,m][1,m] 内的整数序列 aa,小 M 用如下方式定义它的价值 f(a)f(a):

  • 初始系数 X=1X=1;
  • 有 n−1n-1 个机器人,编号分别为 11 至 n−1n-1,每个机器人分别做恰好一次检查;
  • 第 ii 个机器人会检查是否对所有 1≤j≤i1\le j\le i 都满足
aj=an−i+j.a_j=a_{n-i+j}.

若全部满足,则将 XX 改为 X⋅wiX\cdot w_i;否则 XX 不变;

  • 最后记序列的价值为 f(a)=Xf(a)=X。

小 M 想知道,在序列 aa 的每个位置 aia_i 都均匀独立随机生成的情况下,f(a)f(a) 的期望是多少。你只需要求出其在模 998244353998244353 意义下的结果。

输入格式

输入第一行包含三个整数 c,n,mc,n,m,分别表示测试点编号、序列长度和元素范围。c=0c=0 表示该测试点为样例。

输入第二行包含 n−1n-1 个非负整数 w1,w2,…,wn−1w_1,w_2,\ldots,w_{n-1},表示每个机器人的系数。

输出格式

输出一行一个非负整数,表示序列价值的期望对 998244353998244353 取模后的结果。

样例 1 输入

0 3 2
3 2

样例 1 输出

249561091

样例 1 解释

  • 当 a=[1,1,1]a=[1,1,1] 或 a=[2,2,2]a=[2,2,2] 时,f(a)=3×2=6f(a)=3\times 2=6;
  • 当 a=[1,2,1]a=[1,2,1] 或 a=[2,1,2]a=[2,1,2] 时,f(a)=3f(a)=3;
  • 当 a=[1,1,2]a=[1,1,2]、[2,2,1][2,2,1]、[1,2,2][1,2,2] 或 [2,1,1][2,1,1] 时,f(a)=1f(a)=1。

因此

$$\mathbb E[f(a)] = \frac{6\times 2+3\times 2+1\times 4}{8}=\frac{11}{4}\equiv 249561091\pmod{998244353}.$$

样例 2 输入

0 5 5
1 1 1 1

样例 2 输出

1

样例 2 解释

机器人不会改变 XX 的值,因此对所有序列 aa,f(a)f(a) 均等于 11,故期望也为 11。

数据范围

对于每组测试数据,均有:

  • 2≤n≤8002\le n\le 800;
  • 1≤m≤1051\le m\le 10^5;
  • 0≤wi<9982443530\le w_i<998244353。
测试点编号 n≤n\le 特殊性质
1 5 m≤5m\le 5
2, 3 10 无
4, 5 20
6, 7 50
8 ~ 10 150
11, 12 220
13 300
14, 15 400 wi=0w_i=0
16 无
17, 18 500
19, 20 600
21, 22 700
23 ~ 25 800