2023年8月3日，我参加了 TopCoder SRM 848，结果 Div I 第一题就没做出来，零分完赛。赛后看了其他选手的代码，意识到这其实是一个比较基础的组合数学问题。
Alternate Parity 题目描述
相比于原有的 题目描述， 我决定将其转换为如下形式： 给定两个正整数 X L, 生成一个长度为 L 的数列，要求：
- 数列严格单调递增
- 相邻的两个数字奇偶性不同
- 数列的每个元素为正整数
- 数列最后一个元素 $a_L=X$
求所有合法的序列数量，并对某大质数取模。
解答
可以通过若干步变换，将它转化为一个隔板法（Stars and bars）问题。
a1 的奇偶性
对 X 和 L 的奇偶性分类讨论，一共有四种情况。易证 $(X+L)\%2==0$ <=> $a_1\%2==0$
构建辅助序列 b
数列 a 要求相邻的两个数字奇偶性不同，也就是相邻的元素的差为基数。通过求差值，我们可以定义一个辅助数列 b，使序列中的每一个元素都为偶数。
a1 为奇数
\(b = \left\{ \\ \begin{aligned} & b_1 = a_1 - 1 \\ & b_i = a_i - a_{i-1} - 1 \end{aligned} \right.\)
$\sum_{i=1}^{L}b_i = a_L-L = X-L$
a1 为偶数
\(b = \left\{ \\
\begin{aligned}
& b_1 = a_1 - 2 \\
& b_i = a_i - a_{i-1} - 1
\end{aligned}
\right.\)
$\sum_{i=1}^{L}b_i = a_L-L -1= X-L-1$
数列b的性质
无论 $a_1$ 的奇偶性，数列b都符合：
$b_i \% 2 == 0$
$b_i \geq 0$
构建辅助数列 c 以便用隔板法求解
定义 $c_i = \dfrac{b_i}{2} + 1$, 则 \(c_i \in \mathbb{R}+\)
\[\sum_{i=1}^{L}c_i = L + \dfrac{\sum_{i=1}^{L}b_i}{2}\] \[\sum_{i=1}^{L}c_i = \left\{ \\ \begin{aligned} & \dfrac{X+L}{2}, \text{same_parity} \\ & \dfrac{X+L-1}{2}, \text{diff_parity} \end{aligned} \right.\]求数列c一共有多少种合法的情况，正是 隔板法 的标准模型。
对组合数取模
这个基础问题触及了我的知识盲区。查到的两份资料（A，B）提到，可以使用费马小定理 Fermat’s little theorem 解决这一问题。
比赛复盘
比赛时，我先写出了朴素的 DP 代码 f[L,X] = f[L-1,X-1] + f[L-1,X-3] +...，并把这个表格显示了出来，试图找它的规律。初看起来，这和杨辉三角的形态比较类似，但我没有顺着这个方向思考下去，而试图去优化 DP 方程。赛后看到其他选手的代码，才发现是组合数学的问题。
我的代码存档: https://gist.github.com/Endle/1381aa72eb07fe1c92a5de2ff1cb83f6
抢在官方题解发布前写完了本文，希望搜索引擎们能给我送一些流量。