WA 0

s4CRIF1CbUbbL3AtIAly · 2023-09-20 16:58:01 · 题解

题目大意

求 a_i,b_i 恰好填满 1\sim 2^n 且 \forall f(x) 都满足 \sum f(a_i)=\sum f(b_i) 的一组 a,b。

做法

首先可以发现多项式的条件等价于 \forall k 有 \sum a_i^k=\sum b_i^k。

观察样例，用 s_i 表示每个位置属于 a 还是 b，发现 s=\texttt{abbabaabbaababba...}

所有 b 的位置为 2,3,5,8,9,12,14,15,...。

考虑题目给出的是 2^n，猜测与二进制有关。但是题目范围是 1\sim 2^n，于是考虑将所有数 -1。

再次观察 b 位置，变为 1,2,4,7,8,11,13,14,...。

将它们转为二进制：

\begin{array}{rcl}1_{10}&=&1_2\\2_{10}&=&10_2\\4_{10}&=&100_2\\7_{10}&=&111_2\\8_{10}&=&1000_2\\11_{10}&=&1011_2\\13_{10}&=&1101_2\\14_{10}&=&1110_2\\... & = &...\end{array}

它们的 \text{popcount} 都是奇数！

因此我们猜测分组依据为 \text{popcount} 的奇偶性。

接下来证明这个分组的正确性。

首先有一个简单的引理：

引理 I 若 \forall a_i,b_i\in \mathbb{R},p\in \mathbb{N} 且对于所有 f\leq p 的自然数 f 都有 \sum a_i^f=\sum b_i^f，则 \forall x\in \mathbb{R} 都有 \sum (x+a_i)^f=\sum (x+b_i)^f。

证明：将两式左减右得到 (\sum a_i^f)-(\sum b_i^f)=0，求证 (\sum (x+a_i)^f)-(\sum (x+b_i)^f)。考虑 x^i 的系数为 \binom{f}{f-i}(\sum a_j^{f-i}-b_j^{f-i})，右式显然为 0。

接下来就可以证明正确性，即设 k\in \mathbb{Z^+}，a,b 定义如上且只在 [1,2^n] 内，则有 \sum\limits_{i\in a}i^k=\sum\limits_{i\in b}i^k 对所有 0\leq k<n 都成立。

证明可以参考这篇类似题目的博客。

这时我们还有一个疑问：有没有可能存在多解都满足这个要求？

其实可以证明答案是唯一的。

考察如下关于 c 的线性方程组：

\sum_{i=1}^nc_i\cdot i^k=0

可以直接写成 A\bm x=\bm 0 的形式 .

需要证明：\bm x 中只含 1,-1 的解是唯一的 . 因为 A 可逆（具体考察 Vandermonde 行列式），所以通解是 \bm x=c\bm v 的形式，\bm v 是常量，所以显然唯一 .

一种扩展

类似题目

这个套路比较经典，有几个类似题目：

CF1734F Zeros and Ones
P7468 [NOI Online 2021 提高组] 愤怒的小 N

另外，这个有许多有趣性质的序列称为 Thue-Morse Sequence。

代码

void solve(){
    long long n;int q;
    cin>>n>>q;
    while(q--){
        cin>>n;
        n--;
        int cnt=0;
        for(;n;n>>=1)cnt+=n&1;
        cout<<"XZ"[cnt&1]<<"\n";
    }
}

致谢

jijidawang
zhouyuhang
周子衡
Zhihu laxry