http://darkbzoj.tk/problem/4722
集合这样的集合划分然后相等的问题就是 NP 问题, 下界就是指数, 所以要考虑一些性质.
我们现在只考虑 \(v=1000\) 的情况. 由于所有序列中的数对 \(v\) 取膜, 所以考虑当查询的区间大于长度等于 \(v-1\) 时, 问题一定有解, 因为此时要么有一个数出现了两次, 要么出现了 \(0\).
考虑把范围再缩小一点, 我们知道 \(\log_{3}1000=6.8\), 所以当查询区间大于等于 $2\lceil 6.8 \rceil =7 \(时也是必定存在有解的, 所以现在只需要考虑 \)len\le 13$ 的情况了.
然后 \(len \le 13\) 的情况直接双向搜索. 复杂度 $O(2n3^{7}+n \log n) $ 修改操作相当于求 \(x^{3^k}\), 直接欧拉定理.
不要看了题解觉得很简单就去 rush, 先去看题...
- //@winlere
- #include<tr1/unordered_map>
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<cmath>
- using namespace std; typedef long long ll;
- using namespace std::tr1;
- inline int qr(){
- register int ret=0,f=0;
- register char c=getchar();
- while(c<48||c>57)f|=c==45,c=getchar();
- while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();
- return f?-ret:ret;
- }
- const int maxn=1e5+5;
- int seg[maxn];
- int data[maxn];
- int f[21],F;
- unordered_map<int,int> S;
- int n,m,mod,phi,lit;
- void dfs(const int&now,const int&s,const int&k){
- if(now>lit){
- if(S[s]==123) return;
- if(k==1){S[s]|=1;}
- if(k==2){S[s]|=2;}
- if(k==3){S[s]=123;}
- return;
- }
- dfs(now+1,s+f[now]+1,k|1);
- dfs(now+1,s-f[now]-1,k|2);
- dfs(now+1,s,k);
- }
- void dfs2(const int&now,const int&s,const int&k){
- if(now<=lit){
- if(S.find(-s)!=S.end()){
- int g=S[-s];
- if(g==123) F=1;
- if(k==3) F=1;
- if(k==1&&(g>>1&1)) F=1;
- if(k==2&&(g&1)) F=1;
- }
- return;
- }
- if(F)return;
- dfs2(now-1,s+f[now]+1,k|1);
- dfs2(now-1,s-f[now]-1,k|2);
- dfs2(now-1,s,k);
- }
- inline int getphi(int x){
- int temp=x,ret=x;
- for(int t=2;t*t<=temp;++t)
- if(temp%t==0){
- ret-=ret/t;
- while(temp%t==0) temp/=t;
- }
- if(temp>1) ret-=ret/temp;
- return ret;
- }
- inline void add(const int&pos,const int&tag){
- for(int t=pos;t<=n+1;t+=t&-t) seg[t]+=tag;
- }
- inline int que(const int&pos){
- int ret=0;
- for(int t=pos;t>0;t-=t&-t) ret+=seg[t];
- return ret;
- }
- inline int zhi(const int&base,const int&p){
- int g=phi;
- if(p*log(base)<=log(phi)) g=0;
- int ret=1;
- for(int t=p,b=base%phi;t;t>>=1,b=1ll*b*b%phi)
- if(t&1) ret=1ll*ret*b%phi;
- return ret+g;
- }
- inline int three(const int&base,const int&p){
- int ret=1;
- for(int t=zhi(3,p),b=base%mod;t;t>>=1,b=1ll*b*b%mod)
- if(t&1) ret=1ll*ret*b%mod;
- return ret;
- }
- int main(){
- n=qr();m=qr();mod=qr();
- phi=getphi(mod);
- for(int t=1;t<=n;++t) data[t]=qr();
- for(int t=1,t1,t2;t<=m;++t){
- if(qr()==1){
- t1=qr(); t2=qr();
- if(t2-t1+1>13) puts("Yuno");
- else{
- lit=(t2-t1+1)>>1;
- S.clear();
- for(int t=t1,g;t<=t2;++t) data[t]=f[t-t1+1]=three(data[t],g=que(t))%mod,add(t,-g),add(t+1,g);
- F=0;
- dfs(1,0,0);
- dfs2(t2-t1+1,0,0);
- if(F) puts("Yuno");
- else puts("Yuki");
- }
- }
- else{
- t1=qr(); t2=qr();
- add(t1,1); add(t2+1,-1);
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3217247.html