[Swerc2014 C]Golf Bot

题意：给你N个数字，每次利用这N个数字中最多两个数字进行加法运算，来得到目标中的M个数字。

Solution:

我们先来看看多项式乘法：\(A(x)=\sum_{i=0}^{n-1}a_ix^i\)，\(B(x)=\sum_{i=0}^{n-1}b_ix^i\)，\(C(x)=A(x)B(x)\)

\[c_k=\sum_{i+j=k,0\le i,j\le n}a_ib_jx^k
\]

有没有发现什么？我们可以将a复制一份为b，对于x，如果x在a里出现了，则令\(a_x=b_x=1\)，特别的，令\(a_0=b_0=1\)

然后再将a,b两个多项式相乘，则对于一个数x，若\(c_x\)有值，则x可以被两个数组成，否则不行

Code:

#include<bits/stdc++.h>

#define ll long long

#define Pi acos(-1.0)

using namespace std;

const int N=200001*4;

int n,m,ans,len=1,tim,rtt[N],c[N];

struct cp{double x,y;}aa[N],bb[N];

cp operator + (cp a,cp b){return (cp){a.x+b.x,a.y+b.y};}

cp operator - (cp a,cp b){return (cp){a.x-b.x,a.y-b.y};}

cp operator * (cp a,cp b){return (cp){a.x*b.x-a.y*b.y,a.y*b.x+a.x*b.y};}

void FFT(cp *a,int flag){

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

        if(i<rtt[i]) swap(a[i],a[rtt[i]]);

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

        cp wn=(cp){cos(flag*2*Pi/l),sin(flag*2*Pi/l)};

        for(int st=0;st<len;st+=l){

            cp w=(cp){1,0};

            for(int u=st;u<st+(l>>1);u++,w=w*wn){

                cp x=a[u],y=w*a[u+(l>>1)];

                a[u]=x+y,a[u+(l>>1)]=x-y;

            }

        }

    }

}

int read(){

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}

    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}

    return x*f;

}

int main(){

    int maxx=0;

    n=read();aa[0].x=bb[0].x=1;

    for(int i=1;i<=n;i++){

        int x=read();

        aa[x].x=1,bb[x].x=1;

        maxx=max(maxx,x);

    }

    m=read();++maxx;

    for(int i=1;i<=m;i++) c[i]=read();

    while(len<=(maxx<<1)) len<<=1,++tim;

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

        rtt[i]=(rtt[i>>1]>>1)|((i&1)<<(tim-1));

    FFT(aa,1);FFT(bb,1);

    for(int i=0;i<len;i++) aa[i]=aa[i]*bb[i];

    FFT(aa,-1);for(int i=0;i<len;i++) aa[i].x/=len;

    for(int i=1;i<=m;i++)

        if((int){aa[c[i]].x+0.5}) ans++;

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

    return 0;

}

巴特西

[Swerc2014 C]Golf Bot

Solution:

Code:

最新文章

热门文章