Loading...

洛谷P3760 [TJOI2017]异或和

check评论:0 条 remove_red_eye浏览量:33 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2020-06-16

好久没写了QAQ,快退役了

令 $F_i$ 为序列和为 $i$ 的出现次数,$S_i$ 为前缀和为 $i$ 的出现次数,则 $F_i=\sum\limits_{j=0}^m S_j * S_{i+j}$。

令 $S'$ 为翻转后的 $S$,则 $F_{m-i}=\sum\limits_{j=0}^{m-i} S_j * S'_{m-j-i}$。

NTT 优化卷积即可,时间复杂度 $O(n \log n)$

#include <bits/stdc++.h>
using namespace std;
const int mod=998244353,g=3,M=1000000;
int n,a[100010],s0[4000010],s1[4000010],r[4000010],lim,l;
int ksm(int a,int qaq)
{
    int res=1;
    while(qaq)
    {
        if(qaq&1)
        {
            res=1ll*res*a%mod;
        }
        a=1ll*a*a%mod;
        qaq>>=1;
    }
    return res;
}
void NTT(int *x,int flag)
{
    for(int i=0;i<lim;i++)
    {
        if(i<r[i])
        {
            swap(x[i],x[r[i]]);
        }
    }
    for(int mid=1;mid<lim;mid<<=1)
    {
        int wn=ksm(g,flag==1?(mod-1)/(mid<<1):(mod-1-(mod-1)/(mid<<1)));
        for(int k=0,r=(mid<<1);k<lim;k+=r)
        {
            int w=1;
            for(int i=0;i<mid;i++,w=1ll*w*wn%mod)
            {
                int dx=x[i+k],dy=1ll*w*x[i+mid+k]%mod;
                x[i+k]=(dx+dy)%mod,x[i+mid+k]=(dx-dy+mod)%mod;
            }
        }
    }
    if(!flag)
    {
        int ny=ksm(lim,mod-2);
        for(int i=0;i<lim;i++)
        {
            x[i]=1ll*x[i]*ny%mod;
        }
    }
}
int main()
{
    cin>>n;
    s0[0]=1,s1[M]=1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        a[i]+=a[i-1];
        s0[a[i]]++;
        s1[M-a[i]]++;
    }
    lim=1;
    while(lim<(2000000))
    {
        lim<<=1,++l;
    }
    for(int i=1;i<=lim;i++)
    {
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    }
    NTT(s0,1),NTT(s1,1);
    for(int i=0;i<lim;i++)
    {
        s0[i]=1ll*s0[i]*s1[i]%mod;
    }
    NTT(s0,0);
    int ans=0;
    for(int i=0;i<=M;i++)
    {
        if(s0[i]&1)
        {
            ans^=(M-i);
        }
    }
    cout<<ans;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名