题意：给n个数，m次询问，求和<k的数有多少对。
思路：先统计每个数各多少个，然后构造一个多项式，多项式的指数为每个数，系数为个数。然后用该多项式*该多项式，得到的新的多项式的指数就是任意一对数之和，系数就是和为指数的个数（当然有重复的，后面要去重，去重有两个情况，自己乘自己的部分要减去，还有任意一对都有两种可能所以还要除2），如何快速得到新的多项式，这里套入FFT模板解决。然后就用前缀和统计个数就能O（1）查询了。下面给代码：
#include<iostream> #include<map> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int maxn = 270000; typedef long long LL; const int MOD=1e9+7; const double pi=acos(-1); struct cplx{ double r,i; cplx(double r=0,double i=0):r(r),i(i){} cplx operator +(const cplx &a)const {return cplx(r+a.r,i+a.i);} cplx operator -(const cplx &a)const{ return cplx(r-a.r,i-a.i);} cplx operator *(const cplx &a)const {return cplx(r*a.r-i*a.i,r*a.i+i*a.r);} }f1[maxn*2],f2[maxn],res[maxn*2]; void rader(cplx *f,int len){ int j=len>>1; for(int i=1;i<len-1;++i){ if(i<j)swap(f[i],f[j]); int k=len>>1; while(j>=k){ j-=k; k>>=1; } if(j<k)j+=k; } } void FFT(cplx *f,int len,int t){ rader(f,len); for(int h=2;h<=len;h<<=1){ cplx wn(cos(-t*2*pi/h),sin(-t*2*pi/h)); for(int j=0;j<len;j+=h){ cplx e(1,0); for(int k=j;k<j+h/2;++k){ cplx u=f[k]; cplx v=e*f[k+h/2]; f[k]=u+v; f[k+h/2]=u-v; e=e*wn; } } } if(t==-1)for(int i=0;i<len;i++)f[i].r/=len; } void Conv(cplx *a,cplx *b,int len){ FFT(a,len,1); FFT(b,len,1); for(int i=0;i<len;++i)a[i]=a[i]*b[i]; FFT(a,len,-1); } int cnt[maxn]; LL sum[maxn*2]; int main() { int n,k,t,T,m; scanf("%d",&T); while(T--) { memset(cnt,0,sizeof(cnt)); scanf("%d%d",&n,&m); int maxx=0; for(int i=0;i<n;i++) { scanf("%d",&t); cnt[t]++;//cnt[t] shi x^t de xi shu maxx=max(t,maxx); } // int len=log2(n); // if(pow(2,len)<n) len++; // len=pow(2,len); // cout<<len<<endl; int len=1; while(len<=maxx) len<<=1;len<<=1; for(int j=0;j<len;j++) { f1[j].r=f2[j].r=cnt[j]; f1[j].i=f2[j].i=0; } Conv(f1,f2,len); /*for(int i=0;i<len;i++) { f1[i].r/=len; f1[i].r+=1e-9; }*/ /*for(int i=0;i<len;i++){ if(i==10) break; printf("%lf\n",f1[i].r); }*/ for(int i=0;i<len;i++){ f1[i*2].r-=cnt[i]; if(i) sum[i]=sum[i-1]+(LL)(f1[i].r+0.5); } while(m--){ int x; scanf("%d",&x); printf("%lld\n",(sum[x-1])>>1); } } }