Analogous Sets
Sol
1. 集合 生成函数
将可重集合 \(M\) 映射为生成函数：
\[F(M)=\sum_{m\in M} (\#m)\cdot x^m \]如果 \(M\) 的元素在 \(\mathbb N\) 上取值，那么，\(F(M)\) 是 多项式。
2. \(\theta\) 算子
\[\theta(F) = x\cdot F' \]其中 \(F'=\frac{dF}{dx}\)。
可以论证 \(\theta(FG)=\theta(F)\cdot G+\theta(G)\cdot F\)。证明方法 根据定义。
事实上 \(\theta\) 和 \(\frac d{dx}\) 具有类似性质，但是 我们 \(\theta\) 满足更优的性质。具体来说，\(\theta\) 的结果 是 普通幂，而 \(d/dx\) 的结果 是 下降幂。
3. 莱布尼茨公式
图片指向 baidu baike 链接。
4. 证明
题意 容易 翻译 成，\(A,B\) 两个集合 “Analogous” 的 充要条件 是，
\[A^2(x)-A(x^2)=B^2(x)-B(x^2) \]下证 若 \(A(1)\ne 2^k,k\in\mathbb N\)，且 \(A,B\) 都为有限项多项式，则 \(A=B\)。
如果 我们 具有 足够 的 策略，容易做出 “去除 \(x^2\)” 的 决策。
考虑另一个 要求：\(A(1)=B(1)\)。我们带入 充要条件，容易发现其正确性。
接下来，两边同时取 \(\theta\) 算子，可得
\[(\theta A^2)(x)-(\theta A)(x^2)=.... \]做一下 莱布尼兹，易得
\[2\cdot(\theta A)(x)\cdot A(x)-2\cdot (\theta A)(x)\cdot A(x^2) \]两边同时约去 \(2\)，代入 \(x=1\)，易知
\[(\theta A)(1)\cdot (A(1)-1) = (\theta B)(1)\cdot (B(1)-1) \]此处约定 所有函数名 代指 其 在 \(1\) 处 取值，即 \(F\gets F(1)\)。
然后，由于显然的，\(A(1)\ne2^0\)，所以 \(\theta A=\theta B\)。
接下来，我们尝试反复使用 莱布尼茨公式 在其中 \((n)=2,...\) 的情况。
通过对 \(n\) 归纳，可以得出来
\[\theta^n A=\theta^n B \]然而，上述证明存在 小细节：在 “充要条件” 两边同时取 \(\theta^n\) 时，会得出
\[(\theta^n A)\cdot (A-2^{n-1}) = (\theta^n B)\cdot (B-2^{n-1}) \]我们并不一定可以据此说明 \(\theta^n A=\theta^n B\)，所以，检查 \(A-2^{n-1}\) 是否为 \(0\)。
根据命题假设，其不为 \(0\)。所以可以归纳下去。
那么，我们将得到 这一系列 关于 \(\theta\) 的式子，将其 放在系数上考虑，得到 \(A,B\) 的 系数 的 \(n\) 个方程。
这时我们发现 \(\theta\) 的 核心优势：我们得出来 的 方程，系数矩阵是 范德蒙德矩阵 的 转置。
具体来说：
\[\begin{Bmatrix}1\ 2\ 3\ 4\ ...\\1\ 4\ 9\ 16\ ..\\1\ 8\ 27\ ...\end{Bmatrix} \]所以就是满秩的。我们得到了 足够多 个方程，确定 \(B\) 的所有系数之后，对于 \(A\) 多项式 的一共 \(\deg A\) 个系数，方程 的 解 唯一。
所以
\[A=B \]所以，原题目存在解的 充要条件 是 \(n=2^k\)。这时的构造是 容易 的。
事实上，我做这个题目时，首先直接对 \(4\) 构造，然后发现以此类推 可以 构造 \(n=2^k\)。
然后我就提交了 \(2^k\) 的构造。共约用时 10min。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int n,a[maxn],b[maxn];
signed main() {
freopen("analogous.in","r",stdin);
freopen("analogous.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
while(cin>>n,n)
if(n&(n-1))cout<<"No\n";
else {
int ac=0,bc=0,cur=1;
for(int i=0;i<n/2;++i)
if(__builtin_parity(i))
a[ac++]=cur++,b[bc++]=cur++,b[bc++]=cur++,a[ac++]=cur++;
else b[bc++]=cur++,a[ac++]=cur++,a[ac++]=cur++,b[bc++]=cur++;
cout<<"Yes\n";
for(int i=0;i<n;++i)cout<<a[i]<<' ';cout<<'\n';
for(int i=0;i<n;++i)cout<<b[i]<<' ';cout<<'\n';
}
}