给n个数字,保证每个数小于v。有m个操作
操作1.将区间l~r的数字从a[i]变成a[i]a[i]a[i] % v
操作2.每次询问一个区间中是否可以选出两个下标的集合X,Y,满足:
1.X和Y没有交集
2.设集合X中有一个元素是i,则其对集合X的贡献是a[i] + 1,要求集合X的元素的总贡献和集合Y的元素的总贡献
相等如果可以选出这两个集合,输出 Yuno否则输出 Yuki对于100%的数据,n , m <= 100000 , v <= 1000,数据没有梯度
考虑操作1,三次方不能直接维护,考虑log的或者O(1)的复杂度
O(1),找循环节?不太靠谱,不保证每个数字都有循环节
O(log),快速幂?因为是指数相乘,一个数经过三次这样的运算就变成它的27次方了
O(log),倍增,F[i][j]表示数字i的3的2^j次方的答案啊哈,于是线段树维护区间加
对于询问2,对于一个区间长度位len的区间,它的子集数量时2^{len}-1,它可能的元素个数是1000*len.
所以当len>13时,2^{len}-1>1000*len,必然有两个子集之和相同哈
所以对len<=13的,我们搜索。复杂度是3^{len},每个数有3个情况,在X中,在Y中,两个都不在。复杂度仍然爆炸。
考虑双向搜索,3^{len/2}*log(3^{len}),复杂度还行
CODE
#include <bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
typedef long long ll;
typedef unsigned long long ull;
#define mem(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
const int N = 1e6+1e2;
int v;
inline int read(){
int x=0,flag=1;char c=getchar();
while(!isdigit(c)){if(c=='-')flag*=-1;c=getchar();}
while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return x*flag;
}
int n,m,F[1010][20];
int a[N],sum[N<<2],lazy[N<<2],cov[N<<2];
inline int pushdown(int cur,int x){
if(cov[cur]){
cov[cur<<1|1]+=cov[cur];
cov[cur<<1]+=cov[cur];
cov[cur]=0;
}
return 0;
}
int sss=0;
inline int change(int l,int r,int L,int R,int cur){
if(L<=l&&r<=R) {
sum[cur]++;
return 0;
}
int mid=l+r>>1;
if(L<=mid) change(l,mid,L,R,cur<<1);
if(R>mid) change(mid+1,r,L,R,cur<<1|1);
return 0;
}
inline int ask(int l,int r,int x,int cur){
if(l==r){
return sum[cur];
}
int mid=l+r>>1;
if(x<=mid) return ask(l,mid,x,cur<<1)+sum[cur];
else return ask(mid+1,r,x,cur<<1|1)+sum[cur];
}
int s[20],cnt,tot,MID,flag;
int b[N<<2],p[N<<2];
inline int dfs(int pos,int sum,int cnt){
if(flag) return flag;
if(pos>MID){
if(!cnt) return 0;
b[++tot]=sum;
p[sum+(N<<1)]=1;
if(sum==0&&cnt) flag=1;
return 0;
}
dfs(pos+1,sum+s[pos]+1,cnt+1);
if(flag) return flag;
dfs(pos+1,sum-s[pos]-1,cnt+1);
dfs(pos+1,sum,cnt);
if(flag) return flag;
return flag;
}
inline int check(int sum){
if(p[sum+(N<<1)]) return 1;
return 0;
}
inline int dfs2(int pos,int sum,int cnt,int r){
sss++;
if(flag) return flag;
if(pos>r){
if(!cnt) return 0;
if(sum==0&&cnt)
flag=1;
if(p[sum+(N<<1)])
return flag=1;
return 0;
}
dfs2(pos+1,sum+s[pos]+1,cnt+1,r);
if(flag) return flag;
dfs2(pos+1,sum-s[pos]-1,cnt+1,r);
if(flag) return flag;
dfs2(pos+1,sum,cnt,r);
return flag;
}
inline int get(int x){
int s=ask(1,n,x,1);
int ans=a[x];
for(int i=16;i+1;--i){
if(s&(1<<i))
ans=F[ans][i];
}
return ans;
}
inline int query(int l,int r){
cnt=flag=tot=0;
for(int i=l;i<=r;++i){
s[++cnt]=get(i);
}
std::sort(s+1,s+1+cnt);
MID=(r-l+1)>>1;
dfs(1,0,0);
std::sort(b+1,b+1+tot);
dfs2(MID+1,0,0,r-l+1);
for(int i=1;i<=tot;++i) p[b[i]+(N<<1)]=0;
return flag;
}
int main() {
n=read(),m=read(),v=read();
for(int i=1;i<=1000;++i) F[i][0]=(i*i%v*i)%v;
for(int i=1;i<=19;++i){
for(int j=1;j<=1000;++j){
F[j][i]=F[F[j][i-1]][i-1];
F[j][i]%=v;
}
}
for(int i=1;i<=n;++i)
a[i]=read();
while(m--){
int od=read(),l=read(),r=read();
if(od==2){
change(1,n,l,r,1);
}
if(od==1){
if(r-l+1>13){
printf("Yuno\n");
continue;
}
else{
int x=query(l,r);
if(x)printf("Yuno\n");
else printf("Yuki\n");
}
}
}
return 0;
}
0 条评论