CF286E Ladies' Shop FFT

题目链接

读完题后，我们发现如下性质：

• 在合法且和不超过 $m$ 的情况下，如果 $a_{i}$ 出现，则 $a_{i}$ 的倍数也必出现.
• 所以如果合法，只要对所有数两两结合一次就能得到所有 $a_{i}$ 能凑出的不超过 $m$ 的数，且没有多余的.

那么做法就出来了：

• 只需对 $a_{1}...a_{n}$ 两两结合，如果发现一个新的数被凑出来，而这个数在 $a_{1}...a_{n}$ 没出现过，那么就输出无解，否则，就找出那些不能被两两结合出来的 $a_{i}$，输出即可

对于两两结合的部分，用生成函树 + FFT 加速，记住 $0$ 次项的系数为 $0$

#include<bits/stdc++.h>

#define setIO(s) freopen(s".in","r",stdin)

#define maxn 4000000

#define ll long long

using namespace std;

const double pi=acos(-1.0);

struct cpx

{

	double x,y;

	cpx(double a=0,double b=0) {x=a,y=b; }

	cpx operator+(const cpx b) { return cpx(x+b.x,y+b.y); }

	cpx operator-(const cpx b) { return cpx(x-b.x,y-b.y); }

	cpx operator*(const cpx b) { return cpx(x*b.x-y*b.y,x*b.y+y*b.x); }

}A[maxn];

void FFT(cpx *a,int n,int flag)

{

	for(int i=0,k=0;i<n;++i)

	{

		if(i>k) swap(a[i],a[k]);

		for(int j=n>>1;(k^=j)<j;j>>=1);

	}

    for(int mid=1;mid<n;mid<<=1)

    {

    	cpx wn(cos(pi/mid), flag*sin(pi/mid)),x,y;

    	for(int i=0;i<n;i+=(mid<<1))

    	{

    		cpx w(1,0);

    		for(int j=0;j<mid;++j)

    		{

    			x=a[i+j],y=w*a[i+j+mid];

    			a[i+j]=x+y,a[i+j+mid]=x-y;

    			w=w*wn;

    		}

    	}

    }

    if(flag==-1) for(int i=0;i<n;++i) a[i].x/=(double)n;

}

int ans[maxn],arr[maxn],bu[maxn];

int main()

{

	// setIO("input");

	int n,m,len;

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

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

	for(int i=1;i<=n;++i) bu[arr[i]]++,ans[arr[i]]++;

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

	for(len=1;len<=(m<<1);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;i<=m;++i)

    {

    	if((ll)(A[i].x+0.5)>=1)

    	{

    		if(!bu[i]) { printf("NO\n"); return 0; }

    		ans[i]=0;

    	}

    }

    printf("YES\n");

    int sum=0;

    for(int i=1;i<=m;++i) if(ans[i]) ++sum;

    printf("%d\n",sum);

    for(int i=1;i<=m;++i) if(ans[i]) printf("%d ",i);

	return 0;

}