正解:搜索
解题报告:
首先发现长度为$len$的子集的值域为$[0,vcdot len+len]$,数量为$2^{len}$.所以当$2^{len}geq vcdot len+len$时利用鸽巢原理发现显然是有解的.解得$lengeq 14$.
所以就只要解决$len<14$的范围内的问题了.
把转化后的题目拿出来,发现,噢这不是个折半搜索板子嘛.
复杂度也很对,$O(3^{frac{len}{2}})$.
于是就做完了$QwQ$
嗷关于修改操作,只要每次记录下每个位置乘了多少次,然后在询问的时候如果$len<14$就$O(len)$地修改下,否则就不用管鸭$QwQ$
$over$
然后写完代码过来补点儿细节
好像也没啥,就这个修改操作我本来以为很$easy$后来发现是我想锅了$QAQ$
就修改会修改为$d^{3^k}$.所以这里有两种方法,一种是倍增一种是欧拉.因为欧拉比较好写所以我写的欧拉.就直接用扩展欧拉定理就完事$QwQ$.
但是说一个很迷惑的点,,,就我之前拿我的和倍增的方法拍了下,,,发现那个修改后的值不一样,,,但是都$AC$了,,,我也不知道咋回事$kk$
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; #define il inline #define lf double #define gc getchar() #define ri register int #define rc register char #define rb register bool #define lowbit(x) (x&(-x)) #define rp(i,x,y) for(ri i=x;i<=y;++i) #define my(i,x,y) for(ri i=x;i>=y;--i) const int N=100000+10; int n,m,mod,a[N],tr[N],ph,lim; bool flg; unordered_map<int,int>mp; il int read() { rc ch=gc;ri x=0;rb y=1; while(ch!='-' && (ch>'9' || ch<'0'))ch=gc; if(ch=='-')ch=gc,y=0; while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc; return y?x:-x; } il int phi(ri x) { ri ret=x; for(ri i=2;i*i<=x;i++)if(!(x%i)){ret=ret/i*(i-1);while(!(x%i))x/=i;} if(x>1)ret=ret/x*(x-1);;return ret; } il int power(ri x,ri y){ri ret=1;while(y){if(y&1)ret=1ll*ret*x%mod;x=1ll*x*x%mod;y>>=1;}return ret;} il void ad(ri nw,ri dat){while(nw<=n)tr[nw]+=dat,nw+=lowbit(nw);} il int query(ri nw){ri ret=0;while(nw)ret+=tr[nw],nw-=lowbit(nw);return ret;} void dfs1(ri nw,ri lim,ri sum,ri zt) { if(nw>lim) { if(!zt)return; if(zt==1){if(mp[sum]==2 || mp[sum]==4)mp[sum]=4;else mp[sum]|=zt;return;} if(zt==2){if(mp[sum]==1 || mp[sum]==4)mp[sum]=4;else mp[sum]|=zt;return;} mp[sum]=3;return; } dfs1(nw+1,lim,sum,zt);dfs1(nw+1,lim,sum+a[nw]+1,zt|1);dfs1(nw+1,lim,sum-a[nw]-1,zt|2); } void dfs2(ri nw,ri lim,ri sum,ri zt) { if(nw>lim) { if(zt==1 && mp[-sum]>1){flg=1;return;} if(zt==2 && (mp[-sum]>2 || mp[-sum]==1)){flg=1;return;} if(mp[-sum]==3 || (zt==3 && (mp[-sum] || !sum))){flg=1;return;} return; } dfs2(nw+1,lim,sum,zt);if(flg)return; dfs2(nw+1,lim,sum+a[nw]+1,zt|1);if(flg)return; dfs2(nw+1,lim,sum-a[nw]-1,zt|2); } il int lg(ri x){ri ret=0;while(x>=3)++ret,x/=3;return ret;} il int cal(ri d){ri tmp=0;if(d>lim)tmp=ph;swap(ph,mod);d=power(3,d);swap(ph,mod);return d+tmp;} int main() { n=read();m=read();mod=read();ph=phi(mod);lim=lg(ph);rp(i,1,n)a[i]=read(); while(m--) { ri opt=read(),l=read(),r=read(); if(opt==2)ad(l,1),ad(r+1,-1); else { if(r-l+1>=14){printf("Yuno ");continue;}if(l==r){printf("Yuki ");continue;} rp(i,l,r){ri d=query(i);ad(i,-d);ad(i+1,d);a[i]=power(a[i],cal(d));} flg=0;mp.clear(); dfs1(l,(l+r)>>1,0,0);dfs2(((l+r)>>1)+1,r,0,0);if(flg)printf("Yuno ");else printf("Yuki "); } } return 0; }