【Ynoi2012】D2T1

· · 题解

持续推销博客

一道分明就是数学题的YNOI题。

<!--more-->

看到v这么小，觉得大不对。然后看着操作1，你会突然想起一个熟知的结论（？）：区间长度大于\lceil log_2v\rceil肯定无解。证明应该也是较为容易的，你假设当前区间有a_1,a_2,...,a_k这么些数（区间长度不一定为k），那么若当前区间无解说明剩下的数不存在a_1,a_2,...,a_k,a_1+a_2,|a_1-a_2|,...之类的，这样一共有3^k个数。去掉相同的，可以证明有一个上界是2^k-1。你构造2^0,2^1,...,2^{k-1}，这样正好能表示2^0到2^k-1的所有数，首先证明了存在性。另一方面，你假设其中有一个数不是2^m，就假定2^{k-1}没有，变成A。那么2^0到2^{k-1}-1还是完全能表示，若A>2^{k-1}，则又会多出2^{k-1}-1+1=2^{k-1}个数，于是还是2^k-1。若A\leq 2^{k-1}，则只会变少不会变多。于是乎，按照上述归纳一下，就可以证明有一个上界是2^k-1（大概？）。所以就有了那个熟知的结论。

有了结论之后，剩下来的区间都是小于等于10的了。你暴力dfs一下，若当前子集和出现过了，则说明有解（就算集合有交去掉交的部分还是相等的），于是就可以2^{10}的判断其余情况。

区间立方的话，你就在线段树上打个标记，+1表示有一次立方操作。询问的时候暴力递归线段树的那个区间到叶子，那么每个数要做的次数就知道了。由于3^n有点大，所以利用扩展欧拉定理，讨论一下就好了。至于判3^p与phi(v)的大小关系，取对数就可以了。

总复杂度是(假社n,m同阶)O(n(logn(logn+logv)+2^{10}))，轻松跑过去了。

code:

//2019.10.1 by ljz
//email [email protected]
//if you find any bug in my code
//please tell me
#include<bits/stdc++.h>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
//using namespace __gnu_cxx;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f
#define unl __int128
#define eps 5.6e-8
#define RG register
#define db double
#define pc(x) __builtin_popcount(x)
#define ctz(x) __builtin_ctz(x)
//#define pc(x) __builtin_popcountll(x)
typedef pair<int,int> Pair;
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pb push_back
#define ull unsigned LL
#define lowbit(x) (x&-x)
#define gc getchar
//#define kcz 1000000007
//template <class T>using Tree=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
//inline char gc() {
//    static char buf[100000],*p1,*p2;
//    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
//}
inline int read() {
    res s=0,ch=gc();
    while(ch<'0'||ch>'9')ch=gc();
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
    return s;
}
//char sr[1<<21],z[20];
//int C=-1,Z=0;
//inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
//inline void print(res x){
//    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
//    while(z[++Z]=x%10+48,x/=10);
//    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
//}
//inline int read() {
//    res s=0,ch=gc(),w=1;
//    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();}
//    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
//    return s*w;
//}
inline LL Read() {
    RG LL s=0;
    res ch=gc();
    while(ch<'0'||ch>'9')ch=gc();
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
    return s;
}
//inline LL Read() {
//    RG LL s=0;
//    res ch=gc(),w=1;
//    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();}
//    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
//    return s*w;
//}
//inline void write(RG unl x){
//    if(x>10)write(x/10);
//    putchar(int(x%10)+'0');
//}
//inline void swap(res &x,res &y) {
//    x^=y^=x^=y;
//}
int kcz;
//inline void add(res &x,const res &y){
//    x+=y,x>=kcz?x-=kcz:(x<0?x+=kcz:1);
//}
//inline int Add(const res &x,const res &y){
//    return x+y>=kcz?x+y-kcz:(x+y<0?x+y+kcz:x+y);
//}
inline int mul(const res &x,const res &y,const res &KCZ){
    return int(1LL*x*y%KCZ);
}
//inline int sqr(const res &x){
//    return mul(x,x);
//}
//inline int mul(const res &x,const res &y,const res &d){
//    return int(1LL*x*y/d%kcz);
//}
inline int qpow(res x,res y,res KCZ){
    res ret=1;
    while(y){
        if(y&1)ret=mul(ret,x,KCZ);
        x=mul(x,x,KCZ),y>>=1;
    }
    return ret;
}
inline int Qpow(res x,res y){
    res ret=1;
    while(y){
        if(y&1)ret*=x;
        x*=x,y>>=1;
    }
    return ret;
}
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//clock_t start=clock();
//inline void ck(){
//    if(1.0*(clock()-start)/CLOCKS_PER_SEC>0.1)exit(0);
//}
const int N=100000+10;
namespace MAIN{
    int n,m;
    int a[N];
    int val[N<<2];
    int phi;
    void modify(res rt,res l,res r,const res &L,const res &R){
        if(L<=l&&r<=R){val[rt]++;return;}
        res mid=(l+r)>>1;
        if(L<=mid)modify(rt<<1,l,mid,L,R);
        if(R>mid)modify(rt<<1|1,mid+1,r,L,R);
    }
    void get(res rt,res l,res r,const res &L,const res &R){
        if(l==r){
            if(log(3)*val[rt]>=log(phi))a[l]=qpow(a[l],qpow(3,val[rt],phi)+phi,kcz);
            else a[l]=qpow(a[l],Qpow(3,val[rt]),kcz);
            val[rt]=0;
            return;
        }
        if(val[rt])val[rt<<1]+=val[rt],val[rt<<1|1]+=val[rt],val[rt]=0;
        res mid=(l+r)>>1;
        if(L<=mid)get(rt<<1,l,mid,L,R);
        if(R>mid)get(rt<<1|1,mid+1,r,L,R);
    }
    bool fl[1024*10+10];
    int vec[1024+10],vecx;
    bool dfs(res now,res sum,const res &r){
        if(now==r+1){
            if(fl[sum])return 1;
            fl[vec[++vecx]=sum]=1;
            return 0;
        }
        if(dfs(now+1,sum,r))return 1;
        if(dfs(now+1,sum+a[now]+1,r))return 1;
        return 0;
    }
    inline void MAIN(){
        n=read(),m=read(),kcz=read();
        for(res i=1;i<=kcz;i++)if(__gcd(kcz,i)==1)phi++;
        for(res i=1;i<=n;i++)a[i]=read();
        while(m--){
            res opt=read(),l=read(),r=read();
            if(opt==1){
                if(r-l+1>10)puts("Yuno");
                else {
                    get(1,1,n,l,r);
//                    for(res i=l;i<=r;i++)printf("%d ",a[i]);
//                    puts("");
                    if(dfs(l,0,r))puts("Yuno");
                    else puts("Yuki");
                    for(res i=1;i<=vecx;i++)fl[vec[i]]=0;
                    vecx=0;
                }
            }
            else modify(1,1,n,l,r);
        }
    }
}
int main() {
//    srand(19260817);
//    freopen("path.in","r",stdin);
//    freopen("path.out","w",stdout);
    MAIN::MAIN();
//    Ot();
    return 0;
}