1 条题解

  • 1
    @ 2026-10-8 10:09:46

    赛后的做法。

    首先,我们发现若区间存在两个相同元素,那么一定有解。

    根据鸽笼原理,当区间长度大于等于VV时一定有解。

    此时,我们需要解决的的区间满足元素互不相同。

    我们注意到,一个集合非常容易有解,很难构造出很大的无解集合。

    打表发现,当V≤20V \le 20时,最大的无解集合大小为55。

    所以考虑相对暴力的做法。我们使用bitset来维护一些元素经过添加正负号(或弃用)之后,能够组成的数。这相当于一个可行性背包。

    对于某个数xx,若前面的数能组成−x-x或xx则有解。

    对于修改,用分块维护,扩展欧拉定理降幂。可能有更好的做法。

    复杂度O(mn+mvaω)O(m \sqrt n + \frac{mva}{\omega})。其中aa是最大不合法集合大小。

    代码:

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    #define lb(x) (x&(-x))
    #define _Y "Yuno\n"
    #define _N "Yuki\n"
    int n,m,V;
    const int N=1e5+1000,B=400;
    int a[N];
    int tms[N],tk[N];
    inline int K(int x){
    	return (x-1)/B+1;
    }
    int phi; 
    int pw[1010][2010];
    int f3[N];
    int hve[1010];
    signed main(){
    	ios::sync_with_stdio(0);
    	cin.tie(0);
    	cin>>n>>m>>V;
    	for(int i=1;i<=V;i++){
    		if(__gcd(i,V)==1) phi++;
    	}for(int i=1;i<V;i++){
    		pw[i][0]=1;
    		for(int j=1;j<=2*phi;j++){
    			pw[i][j]=pw[i][j-1]*i%V;
    		}
    	}f3[0]=1;
    	for(int i=1;i<=100000;i++){
    		f3[i]=f3[i-1]*3;
    		if(f3[i]>=phi){
    			f3[i]=f3[i]%phi+phi;
    		}
    		
    	}
    	for(int i=1;i<=n;i++){
    		cin>>a[i];
    	}
    	int cnt=0;
    	for(int t=1;t<=m;t++){
    		int op,l,r;
    		cin>>op>>l>>r;
    		if(op==1){
    			cnt++;
    			if(r-l+1>V){
    				cout<<_Y;
    				continue;
    			}for(int i=1;i<=V;i++) hve[i]=0;
    			int flag=0;
    			for(int i=l;i<=r;i++){
    				int val=pw[a[i]][f3[tms[i]+tk[K(i)]]]+1;
    				if(hve[val]){
    					flag=1;break;
    				}hve[val]=1;
    			}if(flag){
    				cout<<_Y;
    				continue;
    			}
    			
    			const int D=5000;//5000过了,想保守一点可以开大一些 
    			bitset<D*2+100>vis;
    			vis[D]=1;
    			for(int i=1;i<=V;i++){
    				if(hve[i]==0) continue;
    				if(vis[D+i]==1||vis[D-i]==1){
    					flag=1;break;
    				}vis=((vis|(vis<<i))|(vis>>i));
    			}
    			if(flag==1){
    				cout<<_Y;continue;
    			}cout<<_N;
    		}else{
    			if(K(l)==K(r)){
    				for(int i=l;i<=r;i++) tms[i]=tms[i]+1; 
    			}else{
    				for(int i=l;i<=K(l)*B;i++) tms[i]=tms[i]+1;
    				for(int i=K(r)*B-B+1;i<=r;i++) tms[i]=tms[i]+1;
    				for(int i=K(l)+1;i<K(r);i++) tk[i]=tk[i]+1;
    			}
    		}
    	}
    	return 0;
    }
    

    题外话:

    在调试这道题时,我在SYOJ上看到了如下的错误信息:

    Wrong Answer 0读取到 Yes,应为 Yuno。

    所以我合理推测,赛时的挂零是因为题面与数据不符导致的

    • 1

    信息

    ID
    887
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    41
    已通过
    3
    上传者