目录
- C - Ants on a Circle
- D - Pilling Up
- E - Placing Squares
C - Ants on a Circle
把掉头视作穿过，然后容易得到最后每只蚂蚁的位置。只需要确定哪只蚂蚁是 \(1\) 号蚂蚁。
统计有多少只蚂蚁穿过了 \(x=M−0.5\) 这个位置即可。
D - Pilling Up
相当于取出来一个又放进去一个，不妨把这个过程刻画到平面图上，去掉首尾，那么就是统计只能向三个方向走，起点为 \((0, 0), (1, 0), \dots, (N - 1, 0)\)，不能越过 \(y = 0\) 与 \(y = N - 1\)，形状不同的路径数量。
一个避免数重的简单方法是，枚举第一个碰到下边界的点，然后把两边的方案乘起来。
E - Placing Squares
嗯拆组合意义：
- 有黑球、红球、蓝球三种球；
- 每个位置上最多放一个黑球，有的位置不能放黑球。
- 记两个相邻的黑球的位置分别为 \(x, y\)（\(x < y\)），那么 \([x, y)\) 之间有恰好一个红球和一个蓝球。
记录所有可能的状态，使用矩阵快速幂优化转移即可。