【UER #12】电子运动
考虑手动模拟一下电子的运动过程。
假设舱室序列为 ++-+--+++-+，初始电子在第 \(6\) 个舱室。
接下来，电子会向左运动到第 \(4\) 个舱室，状态变为 ++-++++++-+。
接下来，电子会向右运动到第 \(10\) 个舱室，状态变为 ++--------+。
接下来，电子会向左运动到第 \(2\) 个舱室，状态变为 +++++++++++。
接下来，电子会向右运动到最右端，状态变为 +----------。
在移动过程中，我们发现了如下事实：
- 电子每向右移动一次，
+的数量减 \(1\)。电子每向左移动一次，+的数量加 \(1\)。
考虑电子一开始在舱室 \(x\)，且初始状态 + 的个数为 \(t\)，则有两种情况：
-
电子运动到最左端，最后的答案为 \(t + x\)
-
电子运动到最右端，最后的答案为 \(t + x - (n+1)\)
显然最终的 + 个数在 \(0\) 到 \(n\) 之间。
同时根据上面的模拟来看，不可能存在电子无法结束运动的情况。
因此，我们猜测最终的答案为 \((t+x) \bmod (n+1)\)。
这是正确的，因为两种答案里一定恰好有一种成立，并且两种答案在模意义下同余。
接下来我们需要考虑 \(x\) 和 \(t\) 的分布。
首先对于 \(x\) 的分布，就是题面中的 \(p\)。
接下来对于 \(t\) 的分布，显然是二项式系数，容易求出。
最后我们求出 \(x\) 和 \(t\) 的卷积，就可以算出答案了。
时间复杂度 \(O(n \log n)\)。