JZTXT

做题记录：P5072 [Ynoi2015] 盼君勿忘

发布时间 2023-06-22 00:01:09作者: 灵长同志

Ynoi 4血！我永远喜欢珂朵莉！

原题链接

珂朵莉给了你一个序列，每次查询一个区间 [l,r][l,r] 中所有子序列分别去重后的和\pmod p(modp)。

首先这是一个静态问题，还不强制在线，而且是 Ynoi 的黑题。

于是们就可以想到大概是一个离线算法，并要求解序列问题。

莫队算法

首先我们有一个定理：

长度为 nn 的序列，一共有 2^n2n 个子序列，其中如果一个元素出现了 mm 次，那么包含该元素的子序列一共有 2^{{n-m}}(2^m-1)2n−m(2m−1) 个。

如何证明？

区间子序列的数量为：

\sum_{i=0}^{n}C_n^i=2^ni=0∑n​Cni​=2n

当一个元素出现 mm 次时，不包含该元素的子序列个数:

2^{n-m}2n−m

为什么？实际上这是相当于给你了一个长度为 n-mn−m 的序列（删去了中间的 mm ）个元素。

很好，证明完毕。

于是我们只需要用莫队维护一下出现次数等于 xx 的点，存在数组 sum[x]sum[x] 里。

对于用链表维护一下不同的出现次数。

最后根据上面的定理统计答案即可。

需要注意的是，对于查询来说，我们要提前预处理出 2^{1}21 到 2^{\sqrt{n}}2n​ 对 pp 取模的值，再预处理出 2^{\sqrt{n}}2n​ 到 2^{n}2n 对 pp 取模的值。

这样我们就可以表示出 11 到 nn 中所有的数的 2^k \pmod p2k(modp) 的值。

这是计算答案部分的代码：

inline void calc_pre(int p){
    pow1[0]=pow2[0]=1;
    for(int i=1;i<=block;i++)pow1[i]=(1ll*pow1[i-1]*2)%p;
    pow2[1]=(pow1[block]%p);
    for(int i=2;i<=block;i++)pow2[i]=(1ll*pow2[i-1]*pow2[1])%p;
}
inline int calc(int x,int p){
    return 1ll*pow1[x%block]*pow2[x/block]%p;
}
inline int query(int l,int r,int p){
    calc_pre(p);
    int res=0;
    for(int i=st.nxt[0];i;i=st.nxt[i]){
        res+=1ll*sum[i]*(calc(r-l+1,p)-calc(r-l+1-i,p))%p;
        res=(res%p+p)%p; 
    }
    return res;
}

这是莫队的核心：

inline void add(int x){
    if(cnt[a[x]]){
        sum[cnt[a[x]]]-=a[x];
        if(!sum[cnt[a[x]]])st.del(cnt[a[x]]);
    }
    cnt[a[x]]++;
    if(!sum[cnt[a[x]]])st.insert(cnt[a[x]]);
    sum[cnt[a[x]]]+=a[x];
}
inline void del(int x){
    sum[cnt[a[x]]]-=a[x];
    if(!sum[cnt[a[x]]])st.del(cnt[a[x]]);
    cnt[a[x]]--;
    if(cnt[a[x]]){
        if(!sum[cnt[a[x]]])st.insert(cnt[a[x]]);
        sum[cnt[a[x]]]+=a[x];
    }
}

这是主函数:

signed main(){
    scanf("%d%d",&n,&m);
    block=sqrt(n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),pos[i]=(i-1)/block+1;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].p);
        q[i].id=i;
    }
    sort(q+1,q+m+1);
    for(int i=1;i<=m;i++){
        while(q[i].r>r)add(++r);
        while(q[i].l<l)add(--l);
        while(q[i].r<r)del(r--);
        while(q[i].l>l)del(l++);
        ans[q[i].id]=query(q[i].l,q[i].r,q[i].p)%q[i].p;
    } 
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}

这是链表：

struct list_LZ{
    int nxt[N],pre[N],tail=0;
    void insert(int x){
        nxt[tail]=x;
        pre[x]=tail;
        tail=x;
    }
    void del(int x){
        if(x!=tail){
            nxt[pre[x]]=nxt[x];
            pre[nxt[x]]=pre[x];
        }else tail=pre[x];
        nxt[x]=pre[x]=0;
    }
}st;

完整代码：

#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 100005
#define ll long long
using namespace std;
int n,m,a[N],cnt[N],sum[N],pow1[3000],pow2[3000],l=1,r=0,tot,ans[N];
int pos[N],block;
struct Q{
    int l,r,id,p;
    bool operator<(const Q &a)const{return pos[l]==pos[a.l]?(pos[l]&1?r<a.r:r>a.r):l<a.l;}
}q[N];
struct list_LZ{
    int nxt[N],pre[N],tail=0;
    void insert(int x){
        nxt[tail]=x;
        pre[x]=tail;
        tail=x;
    }
    void del(int x){
        if(x!=tail){
            nxt[pre[x]]=nxt[x];
            pre[nxt[x]]=pre[x];
        }else tail=pre[x];
        nxt[x]=pre[x]=0;
    }
}st;
inline void add(int x){
    if(cnt[a[x]]){
        sum[cnt[a[x]]]-=a[x];
        if(!sum[cnt[a[x]]])st.del(cnt[a[x]]);
    }
    cnt[a[x]]++;
    if(!sum[cnt[a[x]]])st.insert(cnt[a[x]]);
    sum[cnt[a[x]]]+=a[x];
}
inline void del(int x){
    sum[cnt[a[x]]]-=a[x];
    if(!sum[cnt[a[x]]])st.del(cnt[a[x]]);
    cnt[a[x]]--;
    if(cnt[a[x]]){
        if(!sum[cnt[a[x]]])st.insert(cnt[a[x]]);
        sum[cnt[a[x]]]+=a[x];
    }
} 
inline void calc_pre(int p){
    pow1[0]=pow2[0]=1;
    for(int i=1;i<=block;i++)pow1[i]=(1ll*pow1[i-1]*2)%p;
    pow2[1]=(pow1[block]%p);
    for(int i=2;i<=block;i++)pow2[i]=(1ll*pow2[i-1]*pow2[1])%p;
}
inline int calc(int x,int p){
    return 1ll*pow1[x%block]*pow2[x/block]%p;
}
inline int query(int l,int r,int p){
    calc_pre(p);
    int res=0;
    for(int i=st.nxt[0];i;i=st.nxt[i]){
        res+=1ll*sum[i]*(calc(r-l+1,p)-calc(r-l+1-i,p))%p;
        res=(res%p+p)%p; 
    }
    return res;
}
signed main(){
    scanf("%d%d",&n,&m);
    block=sqrt(n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),pos[i]=(i-1)/block+1;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].p);
        q[i].id=i;
    }
    sort(q+1,q+m+1);
    for(int i=1;i<=m;i++){
        while(q[i].r>r)add(++r);
        while(q[i].l<l)add(--l);
        while(q[i].r<r)del(r--);
        while(q[i].l>l)del(l++);
        ans[q[i].id]=query(q[i].l,q[i].r,q[i].p)%q[i].p;
    } 
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}

才 8282 行，好短。

完结撒花！我永远喜欢珂朵莉！