Codeforces 286E - Ladies' Shop（FFT）

好久没刷过 FFT/NTT 的题了，写篇题解罢（

首先考虑什么样的集合 \(T\) 符合条件。我们考察一个 \(x\in S\)，根据题意它能够表示成若干个 \(\in T\) 的数之和，这样一来我们可以分出两种情况，如果 \(x\) 本来就属于 \(T\)，那么 \(x\) 自然就符合条件，这种情况我们暂且忽略不管。否则根据题设，必然存在一个数列 \(b_1,b_2,\cdots,b_m\)，满足 \(m\ge 2,\forall i\in[1,m],b_i\in T\)，且 \(\sum\limits_{i=1}^mb_i=x\)。由于 \(m\ge 2\)，我们可以将第一项与后面 \(m-1\) 项分开来，即 \(b_1+\sum\limits_{i=2}^mb_i\)。根据题意前两个应当都 \(\in S\)，也就是说如果一个数 \(x\) 可以表示成两个及以上的 \(T\) 中的数的和的必要条件是 \(\exists y,z\in S,s.t.y+z=x\)，因此我们假设 \(S'\) 为可以表示成两个 \(S\) 中元素之和的 \(x\) 组成的集合，那么考虑分以下几种情况考虑：

如果存在一个 \(x\in S'\) 但不属于 \(S\)，那么根据题意可知 \(x\) 也应当可以被 \(T\) 中元素表示出来，与条件不符。
如果不存在属于 \(S'\) 但不属于 \(S\) 的 \(S\)，那么我们考虑 \(T=\{x|x\notin S',x\in S\}\)，那么 \(T\) 即为所求。为什么呢？首先显然所有 \(x\in S',x\in S\) 的数必须都属于 \(T\)，因为根据之前的分析，所有可以表示成两个即以上 \(T\) 中数的和的数都应当 \(\in S'\)。其次对于所有可以表示成两个及以上的数的 \(x\)，也就是每个集合中的 \(x\)，学过线性代数那一套理论的同学应该明白，删掉这样的 \(x\) 是不影响集合所有数能拼出的数的集合的，这样反复进行下去即可将 \(S'\) 删空，剩余的部分就是集合 \(T\) 了。因此集合 \(T\) 符合条件。

那么怎么求 \(S'\) 呢？其实非常 trivial（）考虑幂级数 \(A(x)=\sum\limits_{i=1}^nx^{a_i}\)，那么 \(S'\) 即为 \(A^2(x)\) 中系数非零且 \(\le m\) 的项组成的集合。FFT 求出即可。

时间复杂度 \(m\log m\)

const int MAXN=1e6;

const int MAXP=1<<21;

const double Pi=acos(-1);

int n,m,a[MAXN+5];

struct comp{

	double x,y;

	comp(double _x=0,double _y=0):x(_x),y(_y){}

	comp operator +(const comp &rhs){return comp(x+rhs.x,y+rhs.y);}

	comp operator -(const comp &rhs){return comp(x-rhs.x,y-rhs.y);}

	comp operator *(const comp &rhs){return comp(x*rhs.x-y*rhs.y,x*rhs.y+y*rhs.x);}

} A[MAXP+5];

int rev[MAXP+5],LEN=1;

void FFT(comp *a,int len,int type){

	int lg=31-__builtin_clz(len);

	for(int i=0;i<len;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<lg-1);

	for(int i=0;i<len;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);

	for(int i=2;i<=len;i<<=1){

		comp W(cos(2*Pi/i),type*sin(2*Pi/i));

		for(int j=0;j<len;j+=i){

			comp w(1,0);

			for(int k=0;k<(i>>1);k++,w=w*W){

				comp X=a[j+k],Y=a[(i>>1)+j+k]*w;

				a[j+k]=X+Y;a[(i>>1)+j+k]=X-Y;

			}

		}

	} if(!~type){

		for(int i=0;i<len;i++) a[i].x=(int)(a[i].x/len+0.5);

	}

}

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1,x;i<=n;i++) scanf("%d",&x),a[x]++;

	for(int i=1;i<=m;i++) A[i].x=a[i];

	while(LEN<=(m+m)) LEN<<=1;FFT(A,LEN,1);

	for(int i=0;i<LEN;i++) A[i]=A[i]*A[i];

	FFT(A,LEN,-1);

//	for(int i=1,v;i<=m;i++) printf("%d%c",(v=(int)(A[i].x))," \n"[i==m]);

	for(int i=1,v;i<=m;i++) if((v=(int)(A[i].x))&&!a[i]) return puts("NO"),0;

	vector<int> res;

	for(int i=1,v;i<=m;i++) if(((v=(int)(A[i].x))>0)^a[i]) res.pb(i);

	printf("YES\n%d\n",res.size());

	for(int x:res) printf("%d ",x);

	return 0;

}

upd on 2021.9.21：真·《好久没刷过》

https://codeforces.ml/contest/1574/problem/F

巴特西

Codeforces 286E - Ladies' Shop（FFT）

最新文章

热门文章