20260929A 翻转

你手上有一个长度为 $2n-1$ 的 $01$ 交替串，并且第一个字符是 $1$。也就是说，初始串形如：

$$1010\cdots 1$$

每次操作可以选择一个长度至少为 $1$ 的连续子串，并要求这个子串本身是 $01$ 交替串，且以 $1$ 开头、以 $1$ 结尾，随后将这个子串中的每一位翻转。

请计算恰好翻转 $k$ 次的操作的方案数。答案对 $998244353$ 取模。

放到数轴上容易观察到操作是一堆金字塔状物，操作一次 $1$ 的个数减一，从左往右计数是拓扑序计数状物，显然不可行。

所以考虑插入，如果叠金字塔的时候才扩展原有区间长度，最后再把多余的 $1$ 随便插插，我们就不需要关心预留长度的问题了，amazing 啊。

剩下的 $(n-k)$ 个 $1$ 插入现有的 $n$ 个位置或 $k$ 个区间的方案是 $(\genfrac{}{}{0ex}{}{n+k}{n-k})$，插入区间时相当于把原有区间分成了三段，所以第 $i$ 个有 $2i-1$ 种选择，故答案为：

$$(\genfrac{}{}{0ex}{}{n+k}{n-k})(2k-1)!!$$

$x!!$ 表示 $1\times 3\times 5\times \cdots \times x$。