P6811 「MCOI-02」Build Battle 建筑大师
诸如这样的序列长为 \(n\)：\(1,2...,m-1,m,1,2,...,m-1,m,1,2,3\)
我们称 \(1,2,...,m-1,m\) 为一个块。
问有多少本质不同的子序列。
如果我们把每个子序列往原序列里面填，每个子序列都有其最小表示法。
如 \(1,2,2,3\) 就被填在第一个块的 \(1,3\) 和第二个块的 \(2,3\)。
我们现在做动态规划，保证计算中必须是最小表示，这样就不会重复。
设 \(f_i\) 表示以 \(i\) 结尾的状态个数。
\(f_i=\sum f_j ,(i-m \le j \le i-1)\)
前缀和 \(f_i=s_{i-1}-s_{i-m-1}\)
所以 \(s_i=2\cdot s_{i-1}-s_{i-m-1}\).
答案是 \(s_n\)。
我们现在试图对不同的 \(m\) 快速的求 \(s_n\).
我们发现 \(s_n\) 跟已下问题等价：
从 \(0\) 跳到 \(n\)，一开始 \(v=1\).
有两种行动方式：
一个是往前跳 \(1\) 步，令 \(v=v\cdot 2\).
或跳 \(m+1\) 步，令 \(v=-v\).
\(s_n\) 为所有跳到 \(n\) 的 \(v\) 的和。
对于每个 \(m\)，直接枚举第二种跳了多少次。
\(Ans_m=\sum_{i=0}^{n/(m+1)}(-1)^i\cdot 2^{n-i(m+1)}\cdot C_{n-i\cdot(m+1)+i}^i\).
复杂度调和级数。