题解：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

。也是可以用韦达定理的。

于是就解决了。

代码

CPP

#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;
}

题解：P11192 [COTS 2021] 菜 Jelo

文章操作

题意

思路

代码

相关推荐

评论

题解：P11192 [COTS 2021] 菜 Jelo