题意
有 \(n\) 个位置， \(m\) 次操作，每次操作选择一个位置向左/右走到第一个没有选择过的位置，一个方案合法，当且仅当每次操作都有一个对应点。
求有多少个不同的操作序列。
Sol
考虑集中注意力。
不难打出对于 \(n, m\) 的表。
2
4 12
6 32 128
8 60 400 2000
10 96 864 6912 41472
12 140 1568 16464 153664 1075648
14 192 2560 32768 393216 4194304 33554432
考虑对于第 \(n\) 列上的每个数，除以 \(2 ^ n\)。
1
2 3
3 8 16
4 15 50 125
5 24 108 432 ..
6 35 196 1029 ..
7 48 320 2048 ..
集中注意力，发现第二列每项都是 \(m ^ 2 - 1\)，考虑第三列。
不难想到第三列应该是和 \(m ^ 3\) 有关，单独提出来，与 \(m ^ 3\) 做差。
16 27 11
50 64 14
108 125 17
196 216 20
320 343 23
\(f_{n, 3} = n ^ 3 - 3n - 2\)。
将第四列提出来。
125 256 131
432 625 193
1029 1296 267
2048 2401 353
再次做差。
125 256 131
432 625 193 62
1029 1296 267 74
2048 2401 353 86
如果你注意力比较好的话，可以一眼看出：
\(f_{n, 4} = n ^ 4 - 6n ^ 2 - 8n - 3\)
很难因式分解。
集中注意力，发现第三列有个 \(n ^ 3 - 2\)，第四列有个 \(n ^ 4 - 3\)。
直接发现 \(f_{n, 3} = (n - 2)(n + 1) ^ 2, f_{n, 4} = (n - 3)(n + 1) ^ 3\)
答案很显然了。
考虑另一种不那么需要注意力的做法。
添加一个点 \(n + 1\)，然后首尾相连形成一个环。
那么题目就是求在这个环上操作 \(m\) 次，不经过第 \(n + 1\) 个点的方案数。
不难看出，第 \(n + 1\) 个点显然是平凡的，考虑引入概率，计算第 \(n + 1\) 个点被选到的概率。
显然计算出概率 \(P\) 乘上 \((2 + 2n) ^ m\) 就是答案。
考虑用 \(S\) 枚举所有操作序列。
\[P = \frac{\sum_S \sum_{S_i} 1}{\sum_Sn + 1} \]化简可得：
\[P = \frac{m}{n + 1} \]不被选到的概率即为：
\[P' = 1 - \frac{m}{n + 1} \] 标签：22,省选,sum,2048,2024,第三列,125,432,注意力 From： https://www.cnblogs.com/cxqghzj/p/18024409