CodeForces 286 E.Ladies'Shop(生成関数+FFT)
Description
n個の異なる数a 1,...,anは、各aiが任意の数字(各数字は任意)を選択することによって構成され、その和がmを超えない限り、その和は必然的に前のn個の数に現れるように、このn個の数の中から最小の数字を選択することが要求される.
Input
1行目の2つの整数n,m、その後n個の正の整数a 1を入力し、...、an (1≤n,m≤106,1≤a1Output
正当なシナリオがある場合はYESを出力し、選択数セットを出力し、そうでない場合はNOを出力する
Sample Input
6 10 5 6 7 8 9 10
Sample Output
YES 5 5 6 7 8 9
Solution
明らかに解があればaiの任意の整数倍(値がmを超えない)はA={a 1,a 2,...,an}にあり,これが満たされなければ解がない.
もし1つの数字がAの中のいくつかの数字の線形の組み合わせによって得ることができるならば、すなわちc=Σi=1 nxiai,xi≧0、xiai∈A,xi>0のため、cは必然的にAの中のいくつかの数字の和であることができて、しかも条件から、いくつかの数字の和もAの中で、だからcは必然的にAの中の2つの数の和を表すことができます
さらに解があるかどうかを判断するのは簡単で、Aが加算に閉じ込められているかどうかを知るだけでいい.
f(x)=1+Σxai,g(x)=f 2(x)を1≦c≦mとすると,[xc]g(x)はA±{0}から2つの数字aを選択し,bはa+b=cを満たすスキーム数⋅2を意味する.
[xc]g(x)≠0かつ[xc]f(x)=0の場合、演算は閉じず、解がない
[xc]g(x)=0ならcは考慮しない
したがって、[xc]g(x)≠0かつ[xc]f(x)≠0の場合を考慮して、選択した数字の最小個数を探し出すだけである
[xc]g(x)=2の場合、まだ解がある場合、cの表現は0+cしかないので、cは選択しなければならない.そうしないとcは表示されない
[xc]g(x)>2の場合、aが存在することを示し、b∈Aはa+b=cを満たし、以前選択したデジタルセットはすでにa,bを表すことができるので、必然的にcを表すことができ、cは選択しない
Code
n個の異なる数a 1,...,anは、各aiが任意の数字(各数字は任意)を選択することによって構成され、その和がmを超えない限り、その和は必然的に前のn個の数に現れるように、このn個の数の中から最小の数字を選択することが要求される.
Input
1行目の2つの整数n,m、その後n個の正の整数a 1を入力し、...、an (1≤n,m≤106,1≤a1
正当なシナリオがある場合はYESを出力し、選択数セットを出力し、そうでない場合はNOを出力する
Sample Input
6 10 5 6 7 8 9 10
Sample Output
YES 5 5 6 7 8 9
Solution
明らかに解があればaiの任意の整数倍(値がmを超えない)はA={a 1,a 2,...,an}にあり,これが満たされなければ解がない.
もし1つの数字がAの中のいくつかの数字の線形の組み合わせによって得ることができるならば、すなわちc=Σi=1 nxiai,xi≧0、xiai∈A,xi>0のため、cは必然的にAの中のいくつかの数字の和であることができて、しかも条件から、いくつかの数字の和もAの中で、だからcは必然的にAの中の2つの数の和を表すことができます
さらに解があるかどうかを判断するのは簡単で、Aが加算に閉じ込められているかどうかを知るだけでいい.
f(x)=1+Σxai,g(x)=f 2(x)を1≦c≦mとすると,[xc]g(x)はA±{0}から2つの数字aを選択し,bはa+b=cを満たすスキーム数⋅2を意味する.
[xc]g(x)≠0かつ[xc]f(x)=0の場合、演算は閉じず、解がない
[xc]g(x)=0ならcは考慮しない
したがって、[xc]g(x)≠0かつ[xc]f(x)≠0の場合を考慮して、選択した数字の最小個数を探し出すだけである
[xc]g(x)=2の場合、まだ解がある場合、cの表現は0+cしかないので、cは選択しなければならない.そうしないとcは表示されない
[xc]g(x)>2の場合、aが存在することを示し、b∈Aはa+b=cを満たし、以前選択したデジタルセットはすでにa,bを表すことができるので、必然的にcを表すことができ、cは選択しない
Code
#includefor(int i=0;i>1]>>1|((i&1)<void fft(cp *x,int len,int sta)
{
for(int i=0;iif(i0]=(cp){1,0};
for(unsigned i=2;i<=len;i<<=1)
{
cp g=(cp){cos(2*pi/i),sin(2*pi/i)*sta};
for(int j=i>>1;j>=0;j-=2)w[j]=w[j>>1];
for(int j=1;j>1;j+=2)w[j]=w[j-1]*g;
for(int j=0;j>1);
for(int l=0;l>1;l++)
{
cp o=b[l]*w[l];
b[l]=a[l]-o;
a[l]=a[l]+o;
}
}
}
if(sta==-1)for(int i=0;ivoid FFT(int *a,int n,int *c)
{
int len=1;
while(len1;
fft_init(len);
for(int i=n/2;i0;
for(int i=0;i1?x[i>>1].b:x[i>>1].a)=a[i];
fft(x,len,1);
for(int i=0;i2;i++)
{
int j=len-1&len-i;
z[i]=x[i]*x[i]-(x[i]-!x[j])*(x[i]-!x[j])*(w[i]+(cp){1,0})*0.25;
}
for(int i=len/2;iint j=len-1&len-i;
z[i]=x[i]*x[i]-(x[i]-!x[j])*(x[i]-!x[j])*((cp){1,0}-w[i^len>>1])*0.25;
}
fft(z,len,-1);
for(int i=0;iif(i&1)c[i]=(int)(z[i>>1].b+0.5);
else c[i]=(int)(z[i>>1].a+0.5);
}
int n,m,f[maxfft],g[maxfft],ans[maxfft];
bool check()
{
for(int i=1;i<=m;i++)
if(f[i])
for(int j=2*i;j<=m;j+=i)
if(!f[j])return 0;
return 1;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int a;
scanf("%d",&a);
f[a]=1;
}
if(check())
{
f[0]=1;
FFT(f,m+1,g);
int res=0;
for(int i=1;i<=m;i++)
{
if(g[i]==2)ans[res++]=i;
if(!f[i]&&g[i])
{
res=-1;
break;
}
}
if(res==-1)printf("NO
");
else
{
printf("YES
");
printf("%d
",res);
for(int i=0;iprintf("%d%c",ans[i],i==res-1?'
':' ');
}
}
else printf("NO
");
return 0;
}