[BZOJ4722] 由乃[鸽巢原理+bitset+倍增]

题意

给定长为 \(n\) 序列 \(a\) ,要求支持两种操作：

\(1.\) 询问在一个区间 \([l,r]\) 中，是否能够选出两个交集为空的集合 $ \rm X?,Y$, 使得 \(\sum_{i\in \rm X}{a_i}=\sum_{j\in \rm Y}{a_j}\)。

\(2.\) 将区间 \([l,r]\) 中的每个数字取立方并对 \(v\) 取模。

\(n\leq 10^5,v\leq 10^3\) .

分析

对于 \(1\) 操作 ,如果区间长度 \(len>13\) 一定有解，因为\(2^{14}>14 \times1000\) ,且此处的幂函数增长速度 \(>\) 一次函数.

此时区间中一定存在两个集合和相同，将交集部分去掉就可以构造出一组解。

否则考虑定义状态 \(f_{i,j}\) 表示前 \(i\) 个数字，和为 \(j\) 是否有方案。

\(f_{i,j}=f_{i-1,j}\ |\ f_{i-1,j-a[i]}\) ,如果某个时刻对于同一个 \(j\) 出现了两种构成方案，表示有解 ,理由同上。

这个过程可以用 \(bitset\) 优化。

对于操作 \(2\) ,用树状数组维护每个数取了几次立方，因为模数比较小，所以可以倍增查找。

时间复杂度 \(O(13n*(logn+\frac{13\times13000}{32}))\).

出发点：鸽巢原理

代码

#include<bits/stdc++.h>
using namespace std;
#define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].last,v=e[i].to)
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define pb push_back
typedef long long LL;
inline int gi(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return x*f;
}
template<typename T>inline bool Max(T &a,T b){return a<b?a=b,1:0;}
template<typename T>inline bool Min(T &a,T b){return b<a?a=b,1:0;}
const int N=1e5 + 7;
int n,m,mod;
int jp[N][18],tr[N],a[N];
bitset<14000>S;
int lowbit(int x){return x&-x;}
void modify(int x,int y){for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=y;}
int query(int x){int res=0;for(int i=x;i;i-=lowbit(i)) res+=tr[i];return res;}
int main(){
    n=gi(),m=gi(),mod=gi();
    rep(i,1,n) a[i]=gi();
    for(int i=0;i<mod;++i) jp[i][0]=i*i%mod*i%mod;//注意是操作次数的倍增数组 
    
    for(int j=1;j<18;++j)
    for(int i=0;i<mod;++i)
    jp[i][j]=jp[jp[i][j-1]][j-1];
    
    int opt,l,r;
    while(m--){
        opt=gi(),l=gi(),r=gi();
        if(opt==1){
            if(r-l+1>=14) {puts("Yuno");continue;}
            S.reset();S[0]=1;
            rep(i,l,r){
                int tmp=query(i),x=a[i];
                for(int j=0;j<18;++j) if(tmp>>j&1) x=jp[x][j];
                if((S&(S<<x+1)).any()) { puts("Yuno"); goto A;}
                S=S|(S<<x+1);
            }
            puts("Yuki");
            A:;
        }else
            modify(l,1),modify(r+1,-1);
    }
    return 0;
}

[BZOJ4722] 由乃[鸽巢原理+bitset+倍增]

原文：https://www.cnblogs.com/yqgAKIOI/p/9794932.html