atcoder#AGC022F. [AGC022F] Checkers

[AGC022F] Checkers

分值:16001600

问题描述

X=10100X = 10^{100}。Inaba 在数轴上有 NN 个棋子,第 ii 个棋子位于坐标 XiX^{i},对于所有 1iN1 \leq i \leq N

每秒钟,Inaba 选择两个棋子 AABB,并将 AA 移动到其当前位置关于 BB 的对称点。之后,BB 被移除。(AABB 可能处于相同的位置,也可能 AA 在移动后与其他棋子处于相同的位置。)

经过 N1N - 1 秒后,将只剩下一个棋子。求这个棋子可能的位置的不同数量,结果对 109+710^{9} + 7 取模。

约束条件

  • 1N501 \leq N \leq 50
  • NN 是整数。

输入

输入通过标准输入提供,格式如下:

NN

输出

打印最终棋子可能位置的不同数量,对 109+710^{9} + 7 取模。

3
12

33 个棋子,分别位于 1010010^{100}1020010^{200}1030010^{300}。我们称它们为 AABBCC

以下是两种(总共 1212 种)可能的移动序列:

  • AA 在第一秒跳过 BB,然后在第二秒让 AA 跳过 CCAA 的最终位置是 2×103002×10200+101002 \times 10^{300} - 2 \times 10^{200} + 10^{100}
  • CC 在第一秒跳过 AA,然后让 BB 在第二秒跳过 CCBB 的最终位置是 2×1030010200+4×10100-2 \times 10^{300} - 10^{200} + 4 \times 10^{100}

总共有 3×2×2=123 \times 2 \times 2 = 12 种可能的移动序列,并且最终的棋子位置各不相同。

4
84
22
487772376

记得输出结果对 109+710^{9} + 7 取模。