BZOJ4722 由乃

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4722

 

首先序列长度大于20一定是Yes
因为考虑长为n的区间,选择方案数有$2^n$种,但权值只有$1000n$种,由于两集合不能相交大体上估计一下是20
经过实践证明数据只需要>=10就是Yes了
于是乎用一个标记永久化的线段树维护单点的值(upd:呃……似乎树状数组就好了……)
小范围$3^n$暴力即可
($3^9=19683$……居然过了……)

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int a[maxn],b[233],siz;
int n,m,v,phi[2333];
int ansx,ansy;
bool dfs(int x){
	if(x==siz+1){
		if(ansx&&ansx==ansy){
			return true;
		}
		return false;
	}
	
	if(dfs(x+1))
		return true;
	
	ansx+=b[x]+1;
	if(dfs(x+1))
		return true;
	ansx-=b[x]+1;
	
	ansy+=b[x]+1;
	if(dfs(x+1))
		return true;
	ansy-=b[x]+1;
	return false;
}

#define id(l,r) ((l+r)|(l!=r))
int s[maxn*2];

void add(int l,int r,int l0,int r0){
	if(l0<=l&&r0>=r){
		s[id(l,r)]++;
		return ;
	}
	int mid=(l+r)>>1;
	if(l0<=mid)add(l,mid,l0,r0);
	if(r0>mid)add(mid+1,r,l0,r0);
}
int Q(int l,int r,int ps){
	if(l==r)return s[id(l,r)];
	int mid=(l+r)>>1,ans=s[id(l,r)];
	if(ps<=mid)ans+=Q(l,mid,ps);
	else ans+=Q(mid+1,r,ps);
	return ans;	
}
int pw(int x,int k,int p){
	int ans=1%p;
	for(;k;k>>=1){
		if(k&1)ans=ans*x%p;
		x=x*x%p;
	}return ans;	
}
int pw(int x,int k){
	int ans=1;
	for(;k;k>>=1){
		if(k&1)ans=ans*x;
		x=x*x;
	}return ans;	
}
int get(int ps){
	int x=a;
	int t=Q(1,n,ps);
	if(t<=15)return pw(x,pw(3,t),v);
	return pw(x,pw(3,t,phi[v])+phi[v],v);
}
int main(){
//	freopen("bzoj4722.in","r",stdin);
	
	
	scanf("%d%d%d",&n,&m,&v);
	for(int i=v;i<=v;i++)
	for(int j=1;j<=i;j++)
		if(__gcd(i,j)==1)
			phi[i]++;	
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	while(m--){
		int op,l,r;
		scanf("%d%d%d",&op,&l,&r);
		if(op==1){
			if(r-l+1>=10)puts("Yuno");
			else{
				ansx=ansy=siz=0;
				for(int i=l;i<=r;i++){
					b[++siz]=get(i);
					//cerr<<b[siz]<<" \n"[i==r];
				}
				puts(dfs(1)?"Yuno":"Yuki");
			}
		}else{
			add(1,n,l,r);
		}
	}
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注