题解

思路

若最终人人都拿到勺子，则每把勺子也恰好被取走一次。

做法

沿圆桌观察，某人取左侧勺子后，为避免相邻者失去勺子，方向会被依次确定，因此成功结果只有两类：所有人都取左侧勺子，或所有人都取右侧勺子。两类结果不同，可以分别计数后相加。

统计全取左侧时，按 $P$ 模拟已经行动的人。人 $p$ 的左侧勺子一定还在；若右邻居尚未行动，右侧勺子也在，此人的惯用手必须允许 L，否则方案数归零；若右邻居已经行动，右侧勺子已被取走，此人的惯用手不影响选择，字符为 ? 时方案数乘二。全取右侧的统计完全对称，只需改为检查左邻居是否行动，并在两把勺子都在时要求 R。两次乘积之和即为答案。

复杂度

时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。