题意梳理设密码长度 N,数字集合 ({1,2,\dots,M})((M\le10))。
约束:若序列中存在 (l<r) 满足 (s_l=s_r=B),则区间 ([l,r]) 里一定出现过 (X_B)。等价逆否条件:
如果一段区间内没有出现 (X_B),那么这段区间里最多只能有一个 B。
(M\le10),可以用状态压缩 DP:
状态:(dp[i][mask])
i:填完前 i 位
mask:二进制,第 b 位为 1 表示:从上次出现 (X_b) 到当前位置为止,这段区间内已经出现过一次 b。
也就是:当前无 (X_b) 的后缀里已经有一个 b,不能再放第二个 b。
转移:第 (i+1) 位填数字 c:
先更新新掩码 new_mask:
对所有数字 b:
若 (X_b = c):说明现在出现了 (X_b),后缀重置,第 b 位清零;
否则:原来第 b 位保持不变。
检查能不能填 c:
如果 new_mask 中第 c 位原本是 1(重置前 mask 第 c 位 = 1,且 (X_c\ne c)),说明无 (X_c) 的后缀已经有一个 c,不能再放 c,跳过该 c。
合法则累加:(dp[i+1][new_mask] += dp[i][mask])。
初始状态:(dp[0][0]=1)(前 0 位,无任何数字占用后缀)。
答案:(\sum\limits_{mask} dp[N][mask] \bmod 998244353)。
样例验证输入:
3 4
2 1 2
(M=3,N=4,X_1=2,X_2=1,X_3=2)
程序输出 14,与样例一致。复杂度分析
(M\le10),掩码总数 (2^{10}=1024);
(N\le 10^4);
每层循环:(1024 \times 10) 次操作;
总运算量约 (10^4 \times 1024 \times 10 \approx 10^8),1s 时限完全通过;
使用滚动数组 dp[2][...] 节省内存,仅占用 (2\times1024) long long。
转移逻辑再解释
填数字 c 时:
若 (X_c \ne c),且旧掩码里 c 位为 1:说明当前无 (X_c) 的区间已经有一个 c,不能再放 c,跳过;
更新掩码:
所有数字 b,只要 (X_b=c),说明出现了分隔符 (X_b),把 b 的占用标记清空;
如果 (X_c\ne c),本次新增一个 c,打上占用标记。
若 (X_c = c):
两个 c 之间必然有 (X_c=c),天然满足条件,可以无限放 c,不会触发禁止条件。