1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
| 好的，我们先明确一下你的想法。
**1. 模型理解**
- 有 \( n \) 个玩家（偶数）坐成一圈，两个骰子开始时在相对的两个玩家手里（即初始距离为 \( n/2 \) 还是 \( n/2 \) 个人之间间隔？）。
- 其实这个“距离”指在圆环上沿着某一方向（比如顺时针）从 A 的骰子到 B 的骰子之间的玩家数（不计持有者）。
- 因为对称，我们可以只考虑一个方向上的间隔人数 \( i \)，\( i \) 的范围是 0 到 \( n \) 吗？要小心，两个骰子可能在同一个玩家手里，也可能在对立位置。
在圆上，如果总玩家数是 \( n \)，两个骰子之间的**最小间隔**（顺时针的人数间隔）记为 \( k \)（\( 0 \le k \le n/2 \)），因为如果 \( k > n/2 \) 我们取 \( n-k \) 作为距离（因为圆对称）。
但更常见建模方法：
定义状态 \( d \) = 顺时针从骰子 A 到骰子 B 的人数（不包括 A 的持有者）。那么 \( d \) 的取值范围 \( 0 \le d \le n-1 \)。
- \( d = 0 \) 表示两个骰子在同一人手里 ⇒ 游戏结束（输）。
- 初始时两个骰子在对立位置，即 \( d = n/2 \)（n 偶数时）。
由于圆对称，状态转移只依赖于 \( d \) 的变化，但要注意左右方向是相对的。
你给的 DP 方程似乎是把 \( d \) 当成一个线性排列的“距离”，转移概率不同。
---
**2. 状态转移推导**
假设当前两个骰子之间的顺时针距离为 \( i \)（\( 1 \le i \le n-1 \)）。
记：
- 左骰子玩家：L
- 右骰子玩家：R（即从 L 顺时针走 i 步到 R）
每个骰子掷出的结果，可能改变 \( i \)。
考虑单个骰子行为：
掷出 1 ⇒ 传给左侧（**注意这里的“左”是玩家的左手边，即逆时针方向**）。
掷出 6 ⇒ 传给右侧（即顺时针方向）。
其他 ⇒ 不动。
---
**注意**：这里关键是要明确“左”和“右”在圆上的方向。假设我们看圆是从上方看，玩家编号顺时针增加。
“左” = 逆时针 = 编号减 1 方向。
“右” = 顺时针 = 编号加 1 方向。
于是：
- 如果 L 掷出 1 ⇒ L 的骰子给了 L 左边的人，那这个人相对于 R 的距离会变化吗？
要小心，**不能直接对两个骰子单独建模再相减**，容易错。更安全的方法：
定义 \( x \) = 从骰子 1 持有者顺时针到骰子 2 持有者的步数（0 到 n-1）。
游戏结束当 \( x = 0 \)（同一个人拿两个骰子）。
初始 \( x = n/2 \)。
我们看一步（两个骰子同时掷）对 x 的影响。
---
**3. 转移概率枚举**
设骰子 A 的持有者为 P，骰子 B 的持有者为 Q，顺时针距离 \( x \)。
每个骰子有三种可能动作：
1. 不动（概率 \( 4/6 = 2/3 \)）
2. 传给左（概率 \( 1/6 \)）
3. 传给右（概率 \( 1/6 \)）
这里的“左”对 P 来说，是逆时针移动一步；“右”对 P 来说，是顺时针移动一步。
同样对 Q。
但移动会影响 \( x \)：
设 P 位置为 0，Q 位置为 \( x \)（沿顺时针）。
我们关心的是经过移动后新的距离 \( x' \)。
要算这个得知道两个骰子的移动方向，这有 9 种组合。
其实我们可以直接用相对位移来算：
- P 传给左边的人 ⇒ P 的位置逆时针 1 ⇒ 从新 P 顺时针到 Q 的距离增加 1（模 n）。
- P 传给右边的人 ⇒ P 的位置顺时针 1 ⇒ 从新 P 顺时针到 Q 的距离减少 1（模 n）。
- P 不动 ⇒ 不影响相对位置的“起点”。
对 Q 类似，但 Q 移动会影响的是“终点”：
- Q 传给左边（逆时针） ⇒ Q 位置逆时针 1 ⇒ 从 P 到新 Q 的距离减少 1。
- Q 传给右边（顺时针） ⇒ Q 位置顺时针 1 ⇒ 从 P 到新 Q 的距离增加 1。
因此：
最终 \( x' = x + \Delta \)
其中 \( \Delta = \) (P 向左时为 +1，P 向右时为 -1，P 不动为 0) + (Q 向右时为 +1，Q 向左时为 -1，Q 不动为 0)？不，这里正负要小心。
更直接地：
\( x' = (Q_{\text{new}} - P_{\text{new}}) \mod n \)
其中位置计算模 n。
P 移动对差值影响：
P 左移（逆时针） ⇒ P 减 1 ⇒ Q - P 增加 1 ⇒ x 增加 1。
P 右移（顺时针） ⇒ P 加 1 ⇒ Q - P 减少 1 ⇒ x 减少 1。
Q 移动对差值影响：
Q 左移（逆时针） ⇒ Q 减 1 ⇒ Q - P 减少 1 ⇒ x 减少 1。
Q 右移（顺时针） ⇒ Q 加 1 ⇒ Q - P 增加 1 ⇒ x 增加 1。
所以变化量 \( \Delta \)：
- 来自 P：左移 +1，右移 -1
- 来自 Q：左移 -1，右移 +1
合起来：
\( \Delta = [\text{P左}?+1:\text{P右}?-1:0] + [\text{Q左}?-1:\text{Q右}?+1:0] \)
于是 \( x' = (x + \Delta) \mod n \)，且我们定义游戏结束是 \( x' = 0 \)，注意这里 x 原本是 1..n-1，Δ 取值在 -2 到 2 之间。
---
**4. 简化模型**
如果 n 很大（比如 100），并且初始 \( x = n/2 \)，那么大部分时间 x 离 0 和离 n 都很远，可以近似看成直线上的随机游走，边界在 0 和 n，到 0 就结束。
但题目要求精确 10 位有效数字，所以必须解精确的 DP。
用 \( E(i) \) = 从距离 i 开始到游戏结束的期望轮数。
已知：
\( E(0) = 0 \)（游戏已经结束）
对 \( 1 \le i \le n-1 \)：
考虑两个骰子各自掷出的 6×6=36 种等可能结果，每种结果对应一个 Δ，从而算出 \( i' = (i + \Delta) \mod n \)。
注意 \( i' = 0 \) 直接结束。
也可以利用对称性：因为圆上，距离 i 和距离 n-i 是对称的（只是谁是 P 谁是 Q 的区别），所以 \( E(i) = E(n-i) \)。
因此可以只算 \( i = 1 \) 到 \( n/2 \) 的状态。
---
**5. 转移概率表**
P 和 Q 各自：
L（左，概率 1/6），R（右，概率 1/6），S（不动，概率 4/6）。
Δ = P左?+1:P右?-1:0 加上 Q左?-1:Q右?+1:0。
枚举：
(P,Q) → Δ
(L,L): +1 + (-1) = 0
(L,R): +1 + (+1) = +2
(L,S): +1 + 0 = +1
(R,L): -1 + (-1) = -2
(R,R): -1 + (+1) = 0
(R,S): -1 + 0 = -1
(S,L): 0 + (-1) = -1
(S,R): 0 + (+1) = +1
(S,S): 0 + 0 = 0
概率：
每个组合概率 = (1/6)*(1/6) 或 (1/6)*(4/6) 等，我们统一乘 1/36：
Δ = +2: (L,R) 一种 ⇒ 概率 1/36
Δ = +1: (L,S) 和 (S,R) ⇒ 概率 (1/6)*(4/6) + (4/6)*(1/6) = 4/36 + 4/36 = 8/36
Δ = 0: (L,L), (R,R), (S,S) ⇒ (1/36)+(1/36)+(16/36)=18/36
Δ = -1: (R,S) 和 (S,L) ⇒ 4/36+4/36=8/36
Δ = -2: (R,L) ⇒ 1/36
检查：1+8+18+8+1=36。
---
**6. DP 方程**
对于 \( 1 \le i \le n-1 \)：
\( E(i) = 1 + \sum_{j=-2}^{2} p_j E( (i+j) \bmod n ) \)
其中 \( p_{+2}=1/36, p_{+1}=8/36, p_0=18/36, p_{-1}=8/36, p_{-2}=1/36 \)。
并且定义 \( E(0) = 0 \)。
由于对称性 \( E(i) = E(n-i) \)，可以设未知数 \( E(1), E(2), \dots, E(\lfloor n/2 \rfloor) \)。
我们只需要解这个线性方程组。
---
**7. 特殊情况边界 i=1**
i=1：
可能的 j: -2, -1, 0, 1, 2
i+j mod n:
-2 ⇒ -1 ≡ n-1 (对称到 E(1) 因为 n=100)
-1 ⇒ 0（结束，E=0）
0 ⇒ 1
1 ⇒ 2
2 ⇒ 3
因此：
\( E(1) = 1 + (1/36)E(1) + (8/36)*0 + (18/36)E(1) + (8/36)E(2) + (1/36)E(3) \)
注意 E(n-1)=E(1), E(n-2)=E(2) 等。
我们要对所有 i=1..50 列出方程。
---
**8. 直接实现 DP 解线性系统（n=100）**
以下是 C++ 实现（使用 long double）：
|
