【BZOJ3509】【CodeChef】COUNTARI
暴力优化一下是n^2的，但这样并不能过。
标算好像是分块做，设每块的大小为V。
对于三个数都在同一块内以及只有一个数在块外的情况，用暴力优化处理，时间复杂度nV⋅V2=nV
对于中间数在块内的情况，设这个块的范围是[L,R]，对所有的ai(i<L)和ai(i>R)分别构造生成函数并相乘，得到多项式，指数表示两数之和，系数表示方案数。然后枚举每个块内的数，看它作为中间数的方案有多少个并加入答案。
这一步需要用FFT，所以时间复杂度为n⋅maxa⋅logmaxaV，取个合适的V就好了。
刚开始我用NTT来做，发现本机上跑得飞快，linux下也跑得飞快，然而交上去就是T。后来改成复数运算后A了。事实证明long long+取模运算在某些地方是不能乱用的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 | #include <cmath>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long LL;const int maxn=100010,V=2000;const double pi=M_PI;inline void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}struct Complex{ double r,i; Complex (double _r=0,double _i=0):r(_r),i(_i){} friend Complex operator + (const Complex &a,const Complex &b); friend Complex operator - (const Complex &a,const Complex &b); friend Complex operator * (const Complex &a,const Complex &b);};Complex operator + (const Complex &a,const Complex &b) {return Complex(a.r+b.r,a.i+b.i);}Complex operator - (const Complex &a,const Complex &b) {return Complex(a.r-b.r,a.i-b.i);}Complex operator * (const Complex &a,const Complex &b) {return Complex(a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r);}int rev[maxn];void FFT(Complex *a,int N,int f){ for (int i=0;i<N;i++) if (i<rev[i]) swap(a[i],a[rev[i]]); for (int i=1;i<N;i<<=1) { Complex wn(cos(M_PI/i),f*sin(M_PI/i)); for (int j=0;j<N;j+=(i<<1)) { Complex w(1,0); for (int k=0;k<i;k++,w=w*wn) { Complex x=a[j+k],y=w*a[j+k+i]; a[j+k]=x+y,a[j+k+i]=x-y; } } } if (f==-1) for (int i=0;i<N;i++) a[i].r/=N;}Complex tempA[maxn],tempB[maxn],tempC[maxn];void Polynomial_Multyply(int *a,int *b,int n,int m,LL *c){ int N=1; while (N<n+m-1) N<<=1; for (int i=0;i<N;i++) rev[i]=(rev[i>>1]>>1)|((i&1)*(N>>1)); for (int i=0;i<n;i++) tempA[i].r=a[i],tempA[i].i=0;for (int i=n;i<N;i++) tempA[i].r=tempA[i].i=0; for (int i=0;i<m;i++) tempB[i].r=b[i],tempB[i].i=0;for (int i=m;i<N;i++) tempB[i].r=tempB[i].i=0; FFT(tempA,N,1);FFT(tempB,N,1); for (int i=0;i<N;i++) tempC[i]=tempA[i]*tempB[i]; FFT(tempC,N,-1); for (int i=0;i<N;i++) c[i]=(LL)(tempC[i].r+0.1);}int a[maxn];int lcnt[maxn],rcnt[maxn];int n;long long ans;void Solve1(){ for (int i=1;i<=n;i++) rcnt[a[i]]++; for (int st=1;st<n;st+=V) { int ed=min(n,st+V-1); for (int i=st;i<=ed;i++) rcnt[a[i]]--; for (int i=st;i<=ed;i++) { for (int j=i+1;j<=ed;j++) { if (a[i]<=(a[j]<<1))ans+=rcnt[(a[j]<<1)-a[i]]; if (a[j]<=(a[i]<<1))ans+=lcnt[(a[i]<<1)-a[j]]; } lcnt[a[i]]++; } }}int A[maxn],B[maxn];LL C[maxn];void Solve2(){ for (int st=V+1;st<n;st+=V) { memset(A,0,sizeof(A)); memset(B,0,sizeof(B)); int ed=st+V-1; if (ed>=n) return; int na=0,nb=0; for (int i=1;i<st;i++) A[a[i]]++,na=max(na,a[i]); for (int i=ed+1;i<=n;i++) B[a[i]]++,nb=max(nb,a[i]); na++,nb++; Polynomial_Multyply(A,B,na,nb,C); for (int i=st;i<=ed;i++) ans+=C[a[i]*2]; }}int main(){ read(n); for (int i=1;i<=n;i++) read(a[i]); Solve1(); Solve2(); printf("%lld\n",ans); return 0;} |
评论 (0)
