题目大意
设 $x=10^{100}$，在数轴上有 $n$ 个点，第 $i$ 个点的坐标为 $x^i$，每次可以将一个点 $A$ 变为关于点 $B$ 的对称点，并把 $B$ 删除，进行 $n-1$ 次这样的操作，问最后能得到多少种不同的坐标。
$n \le 50$
去看了官方的题解，这里给出官方的 $O(n^4)$ 做法和比较完整的证明。
思路
首先，$x$ 特别大，我们可以直接把每个 $x^i$ 看作是互相独立的。$A$ 关于 $B$ 的对称点实际上就是 $2B-A$。
首先观察可以发现，得到的所有数肯定都是长成 $\sum 2^a(-1)^bx^i$ 的形式。
举个例子，比如最后我们得到了 $2x^1+2x^2+x^3-4x^4$，那么我们发现其实只需要把点的顺序调换一下，就可以得到另外一种结果，比如 $2x^1+2x^3+x^2-4x^4$。
所以我们其实只关心最后得到的系数的集合。上面的例子中，我们只关心最后得到的系数集合 ${1, 2, 2, -4}$。
我们寻找这样的系数集合 $A$ 都有什么性质：
-
$\forall i\in A,\, \exists j,\, \rvert i\lvert=2^j$，即集合中每个元素的绝对值都是 $2$ 的次幂。
证明：考虑对称的过程 $2B-A$，那么实际上每个数就是被乘上了若干个 $2$。
-
$\sum_{i\in A}i=1$，即集合中元素的和为 $1$。
证明：考虑归纳法证明。
首先初始值 ${1}$ 的和为 $1$。
若 $A,B$ 集合均满足以上条件，那么新得到的集合 $2B-A$ 的和为 $2 \times 1 - 1 = 1$，得证。
-
若 $2^i$ 或 $-2^i$ 属于 $A$，那么 $2^{i-1}$ 或 $-2^{i-1}$ 也属于 $A$。
证明：同样归纳法证明，如果 $A$ 包含的指数范围为 $[0,a]$， $B$ 包含的指数范围为 $[0,b]$，那么易证 $2B-A$ 包含的指数范围为 $[0,\max(a,b+1)]$。
-
$2^0$ 和 $-2^0$ 中有一个且仅有一个属于 $A$。
证明：归纳法，首先 $2^0,-2^0$ 都不属于 $2B$，而 $A$ 中有 $2^0,-2^0$ 中的其中一个，所以 $2B-A$ 中有且仅有 $2^0,-2^0$ 中的一个。
但是这些性质都还只是必要条件，并不充分。我们有一个充要条件如下：
对于每一个 $i>1$，存在一种将 $A$ 中的所有 $\pm 2^i$ 元素前的正负号进行修改的方案，使得 $\sum_{\rvert x\lvert=2^j,j\in[0,i]}x=1$（即所有指数小于等于 $i$ 的数的和为 $1$）
证明：
-
必要性：
归纳法。
然后对于每一个 $i>1$，将 $B$ 集合中的 $2^{i-1}$ 元素重标正负号后，得到指数范围在 $[0,i-1]$ 内的数的和为 $1$，并将 $A$ 集合中的 $2^i$ 元素重标正负号后，得到指数范围在 $[0,i]$ 内的数的和为 $1$。
那么 $2B$ 的指数范围就是 $[1,i]$，且 $2^i$ 的正负号被重标，那么 $2B-A$ 就也符合上述性质。
对于 $i=1$，根据性质 $4$，一定可以进行重标正负号使得和为 $1$。
-
充分性：
我们想办法构造出一种方案，使得 $C$ 集合能够被分为 $2B-A$，并且 $A,B,C$ 集合均满足以上的所有性质，即可证明充分性。
首先假设 $-2^0 \in C$。
设 $k$ 为最小的正整数使得 $2^k\in C$。如果对于指数范围在 $[1,k-1]$ 内的所有数都出现了大于等于两次，我们可以构造 $B={-2^0,-2^1,\cdots,-2^{k-2},2^{k-1}}$，这样 $2B={-2^1,-2^2,\cdots,-2^{k-1},2^k}$，我们从 $C$ 集合中刨除掉这些元素，再将元素取反，就得到了 $A$ 集合。
首先可以发现 $B$ 集合满足以上的所有性质，并且 $A$ 集合满足以上的 $4$ 条基本性质。
下面是 $A$ 集合满足性质 $5$ 的证明：
首先对于所有的 $i\le k$，$C$ 集合中的 $\pm2^i$ 在重标正负号后，$2^i$ 的个数一定大于 $-2^i$ 的个数，否则和 $<0$，不满足性质 $5$。
那么在重标正负号的结果中，一定存在一个 $2^i$。我们将这个 $2^i$ 分配给 $B$ 集合，将剩下的分配给 $A$ 集合，那么可以证明 $i\le k$ 的时候性质 $5$ 是成立的。
对于 $i > k$，$C$ 集合重标正负号的结果都分配给了 $A$，因为 $C$ 集合的和为 $1$，$B$ 集合的和也为 $1$，那么 $A$ 集合的和肯定也为 $2\times 1 - 1 = 1$，所以也是成立的。
综上，这样构造出来的 $A$ 集合是满足性质 $5$ 的。
如果对于指数范围在 $[1,k-1]$ 内，存在一个数只出现了一次，那么我们发现再按照上面的方式分配，会导致得到的 $A$ 集合不满足性质 $3$。
那么我们记最小的只出现了一次的指数为 $j$。如果 $j=1$，那么我们可以令 $A={2^0}$，并且 $B$ 为剩下的数除以 $2$。对于 $C$ 的每一个前缀和，将它减去第一个元素 $-2^0$ 再除以 $2$ 也等于 $1$，所以 $B$ 集合也是符合性质 $5$ 的。
如果 $j>1$，那么指数范围在 $[0,j-1]$ 内的数的和的最大值应该为 $-2^0+2(-2^1-2^2-\cdots -2^{j-1})=-2^{j+1}+3$，发现这个数永远小于 $-2^j$，那么无论如何修改 $2^j$ 前面的正负号都无法使得前缀和等于 $1$，所以是不存在 $j>1$ 的情况的。
于是我们证明了性质 $5$ 是一个充要条件。
于是，我们只需要统计满足以上五个条件的集合数有多少种即可。
设 $f_{i,j}$ 表示已经放了 $i$ 个元素，并且这些元素的和为 $1+jV$，其中 $V$ 为现在要放的 $2$ 的次幂是多少。
那么我们枚举选了 $a$ 个 $V$，选了 $b$ 个 $-V$，那么元素的和就变为了 $1+(j+a-b)V$。因为下一个填的数就要比现在的数乘 $2$，所以 $f_{i,j}$ 转移到 $f_{i+a+b,\frac{j+a-b}{2}}$。
我们需要满足将这些数任意标正负号之后，和为 $1$，那么我们只需要满足 $j \equiv a+b \pmod 2$ 且 $a+b\ge \rvert j\lvert$ 即可。
然后考虑对这个系数集合分配原来的 $x^i$，这个就是多重组合数的形式（$\frac{n!}{\prod a!}$），我们可以把 $\frac{1}{\prod a!}$ 的部分拆到转移上，也就是 $f_{i,j} \times \frac{1}{a!b!}\rightarrow f_{i+a+b,\frac{j+a-b}{2}}$。
初始状态为 $f_{0,-1}=1$，答案为 $n!f_{n,0}$。
需要注意，为了满足性质 $4$，需要特殊判断一下，当 $i=0$ 时，必须满足 $a+b=1$ 时才可以转移。
Code
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 55, P = 1000000007;
int f[MAXN][MAXN << 1];
int n;
int fac[MAXN], inv[MAXN];
int qpow(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = 1ll * ans * a % P;
a = 1ll * a * a % P;
b >>= 1;
}
return ans;
}
int main() {
scanf("%d", &n);
f[0][MAXN + -1] = 1;
fac[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % P;
inv[n] = qpow(fac[n], P - 2);
for (int i = n; i >= 1; i--) inv[i - 1] = 1ll * inv[i] * i % P;
for (int i = 0; i < n; i++) {
for (int j = -n; j <= n; j++) if (f[i][j + MAXN]) {
for (int a = 0; a <= n; a++) {
for (int b = 0; i + a + b <= n; b++) if ((a || b) && ((j + a + b) % 2 == 0) && a + b >= abs(j)) {
if (i == 0 && a + b != 1) continue;
f[i + a + b][(j + a - b) / 2 + MAXN] = (f[i + a + b][(j + a - b) / 2 + MAXN]
+ 1ll * f[i][j + MAXN] * inv[a] % P * inv[b]) % P;
}
}
}
}
printf("%lld\n", 1ll * f[n][MAXN + 0] * fac[n] % P);
return 0;
}
