题解 P3760 【[TJOI2017]异或和】

2018-01-29 17:02:26


我的FFT一个log被两个log的树状数组按位查询碾压啊qwq

原理大概是前缀和+差分可以得到所有区间的和,统计出每个和出现过多少次,把出现过奇数次的所有和异或起来就可以得到答案

做法大概是先做一遍前缀和,存到权值数组里,正着存一遍反着存一遍再卷积起来(套路)

//不开O2暂时卡不过QAQ

//加了“三次变两次”优化也卡不过QAQ

代码(仅供参考,欢迎帮忙卡常(雾)):

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const double pi=3.1415926535897932384626433832795;
const int MAXV=1000000;
struct c
{
    double r,i;
    inline c(){r=i=0.0;}
    inline c(const double a,const double b){r=a,i=b;}
    inline c operator+(const c &x)const{return c(r+x.r,i+x.i);}
    inline c operator+=(const c &x){return *this=*this+x;}
    inline c operator-(const c &x)const{return c(r-x.r,i-x.i);}
    inline c operator-=(const c &x){return *this=*this-x;}
    inline c operator*(const c &x)const{return c(r*x.r-i*x.i,r*x.i+i*x.r);}
    inline c operator*=(const c &x){return *this=*this*x;}
    inline c operator/=(const int x){r/=x,i/=x;return *this;}
    inline c conj(){return c(r,-i);}
}A[2333333];
int r[2333333],l=1;
int n;
inline void fft(c *a,int ty)
{
    for(int i=0;i<l;i++)i<r[i]?(void)(0):swap(a[i],a[r[i]]);
    for(int i=1;i<l;i<<=1)
    {
        c w(cos(pi/i),ty*sin(pi/i));
        for(int j=0;j<l;j+=i<<1)
        {
            c wn(1.0,0.0);
            for(int k=j;k<i+j;k++)
            {
                c t=a[i+k]*wn;
                a[i+k]=a[k]-t;
                a[k]+=t;
                wn*=w;
            }
        }
    }
}
int a[233333],s[233333];
int tmp[2333333],ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        s[i]=s[i-1]+a[i];
        A[s[i]].r+=1;
    }
    A[0].r+=1;
    for(int i=0;i<MAXV;i++)A[i].i=A[MAXV-i-1].r;
    while(l<=MAXV*2)l<<=1;
    for(int i=1;i<l;i<<=1)
        for(int j=0;j<i;j++)
            r[i+j]=r[j]+l/(i<<1);
    fft(A,1);
    A[l]=A[0];
    for(int i=0;i<=l-i;i++)
    {
        c t=(A[i]+A[l-i].conj())*c(0.0,1.0)*(A[i]-A[l-i].conj());t/=4;
        c t2=(A[l-i]+A[i].conj())*c(0.0,1.0)*(A[l-i]-A[i].conj());t2/=4;
        A[i]=t;A[l-i]=t2;
    }
    fft(A,-1);
    for(int i=0;i<MAXV;i++)tmp[MAXV-i-1]=-A[i].r/l+0.5;
    for(int i=0;i<MAXV;i++)ans^=i*(tmp[i]&1);
    printf("%d\n",ans);
    return 0;
}