昨天 CF ICPC 镜像的 H 咋做？

题目总版

__vector__ @ 2024-11-25 15:17:07

我们队 3 人昨天赛时到最后也没做出来，大概是类似于括号序列的做法。

听说正解是 DP，但是不知道怎么设计状态。

by ssxvngn @ 2024-11-25 15:21:46

@vector

对最后 <, =, > 的序列计数。

设 f_i 为用了 i 个 <, > 的合法方案数，因为 = 不必要最后组合数就行。

然后合法条件就是不能有长度为 k 的同符号连续段，转移容斥就是 f_i = 2f_{i - 1} - f_{i - k}，特殊处理下 f_{k} = 2^k - 2。

by Iceturky @ 2024-11-25 15:22:13

楼上正解

by Iceturky @ 2024-11-25 15:22:48

并不是括号序列，因为小于不对应-1，大于也不对应+1，性质比±1要更强

by __vector__ @ 2024-11-25 15:39:26

@ssxvngn 拜谢巨佬。