题解：P11192 [COTS 2021] 菜 Jelo

· · 题解

题意

构造一个大小为 2^{\frac N 2} 的 \{0,1,\cdots,2^N-1\} 的子集，满足子集中元素两两异或和均不同。

思路

设 n=\dfrac N 2。注意区分大小写。

把一个数拆成前半段和后半段，长度均为 n。由于要构造的集合大小是 2^n，我们猜测前半段任意填，后半段是关于前半段的函数。设前半段为 x\in[0,2^n)，后半段为 f(x)\in[0,2^n)。

既然已经是异或了，我们再用普通的加法乘法肯定不方便。模仿这道题，我们构造有限域 \mathbb F_{2^n}，下面的所有加法和乘法未经说明都是这个有限域里的。

假设存在两对（无序对）元素 \{(a,f(a)),(b,f(b))\},\{(c,f(c)),(d,f(d))\}，满足它们异或和相同。由于我们是拼起来的，前后对于异或独立，所以有方程组 a+b=c+d,f(a)+f(b)=f(c)+f(d)。

我们对 f 的构造要满足这个方程有且仅有两个解，即说明 \{a,b\}=\{c,d\}。

只有两个解那就是二次方程喽。那我们直接让 f 变成二次函数，比如 f(x)=x^2。

带回上面的方程，我们有 a+b=c+d,a^2+b^2=c^2+d^2。

把第一个式子平方减去第二个式子，得到 ab=cd。

和相等，积也相等。这是什么🤔？韦达定理呀。我们有 \{a,b\},\{c,d\} 都是方程 x^2-(a+b)x+ab=0 的一组解，即 \{a,b\}=\{c,d\}。

我们只需要求出 2^n 阶的有限域就可以了。

你高高兴兴写了代码，跑出来一看，n=4 都过不去。

为什么？

在实数域下，平方是不存在逆的。在有限域下用平方是很危险的。

如何解决呢？我们又不想放弃韦达定理。

是不是改成三次方就可以了？

此时 a+b=c+d,a^3+b^3=c^3+d^3，一式立方减二式，得到 ab(a+b)=cd(c+d)，即 ab=cd。也是可以用韦达定理的。

于是就解决了。

代码

#include<bits/stdc++.h>
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i) 
#define ll long long
using namespace std;
int m,p;
inline ll qpow(ll base,int expo){
    ll res(1);
    while(expo){
        (expo&1)&&(res=res&base);
        base=base&base,expo>>=1;
    }
    return res;
}
bool type;
struct poly{
    int num[100]={};
    int len=0;
    inline void init(){
        while(!num[len]&&len>0) --len;
        return;
    }
    inline void turn(int t){
        while(t) num[len++]=t&1,t>>=1;
        init();
        return;
    }
    inline poly operator+(const poly&a)const{
        poly res;
        res.len=max(a.len,len);
        F(i,0,res.len) res.num[i]=num[i]^a.num[i];
        res.init();
        return res;
    }
    inline poly operator+(const int a)const{
        poly res=*this;
        int&qwq(res.num[0]);
        qwq^=a;
        return res;
    }
    inline poly operator-(const poly&a)const{
        return a+*this;
    }
    inline poly operator-(const int a)const{
        return *this+a;
    }
    inline poly operator*(const poly&a)const{
        poly x;
        F(i,0,len) F(j,0,a.len){
            int&qwq(x.num[i+j]);
            qwq^=(a.num[j]&num[i]);
        }
        x.len=len+a.len;
        x.init();
        return x;
    }
    inline poly operator*(const int a)const{
        poly res=*this;
        F(i,0,len){
            int&qwq(res.num[i]);
            qwq=a&qwq;
        }
        return res;
    }
    inline bool operator<=(const poly&a)const{
        if(type) return len<=a.len;
        if(len!=a.len) return len<=a.len;
        R(i,len,0) if(num[i]!=a.num[i]) return num[i]<=a.num[i];
        return 1;
    }
    inline poly operator<<(const int a)const{
        poly res;
        res.len=a+len;
        F(i,0,len) res.num[a+i]=num[i];
        return res;
    }
    inline poly operator%(const poly&a)const{
        poly t=*this;
        while(a<=t){
            poly tmp=a*t.num[t.len];
            t=t-(tmp<<(t.len-a.len));
        }
        t.init();
        return t;
    }
    inline bool check()const{
        poly x=*this,y;
        F(i,2,(1<<m)-1){
            poly t;
            t.turn(i);
            y=x%t;
            if(y.len==0&&y.num[0]==0) return 0;
        }
        return 1;
    }
    inline void output(){
        F(i,0,m) cout<<num[i]<<" ";
        cout<<"\n";
        return;
    }
    inline int decode(){
        int res(0);
        R(i,len,0) res=(res<<1)|num[i];
        return res;
    }
}mod;
inline void findmod(){
    R(i,(1<<m)-1,1){
        poly a;
        a.turn(i);
        a.num[m]=1;
        a.len=m;
        if(a.check()){
            mod=a;
            return;
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0); 
    cin>>m;
    m/=2;
    findmod();
    type=1;
    cout<<(1<<m)<<"\n";
    F(i,0,(1<<m)-1){
        int qwq=i<<m;
        poly qaq;
        qaq.turn(i);
        qwq|=(qaq*qaq*qaq%mod).decode();
        cout<<qwq<<" ";
    }
    return 0;
}