题解：P5527 [Ynoi2012] NOIP2016 人生巅峰

· · 题解

这个结论真的好厉害啊。

思路

我们先考虑查询操作，我们隐隐约约感觉，当值得数量到达一定时，一定有解，而且这个 v 的取值也很奇怪，我们从这里入手。

于是从值域考虑，一个数最大只有 1000，若区间长度为 n，那最大的区间和也只有 1000n，但是数的组合却有 2^n 种，于是，根据抽屉原理，只需要解出 2^n\ge1000n 的最小正整数解即可，随便试一下就发现 14 是最小的一个，于是当区间长度大于等于 14 时，一定有解。

那我们需要处理的区间长度最大也只有 13，但是如果暴力枚举选法有 2^{13}=8192 种可能，居然超时，于是我们可以考虑折半搜索，那么只有 \sqrt{8192} 种可能，可以通过。

区间修改操作则可以用线段树处理，最后的值一定是 a_i^{3^x}\bmod v 的形式，我们只需要记录 x，用拓展欧拉定理求出最后的值即可，因为每次询问不超过十三，所以查询的复杂度只有 \mathcal{O}(13\log{n})。

CODE

复杂度 \mathcal{O}(m\log{n}+m\sqrt{v})

#include<bits/stdc++.h>
using namespace std;
namespace lcy{
    template<typename T>void read(T &x){
//      printf("%d\n",x);
        x=0;int f=1;char ch=getchar();
        while(!isdigit(ch)){
            if(ch=='-')f=-1;
            ch=getchar();
        }
        while(isdigit(ch)){
            x=(x<<3)+(x<<1)+(ch&15);
            ch=getchar();
        }
        x*=f;
    }
    template<typename T,typename ...Args>
    void read(T &x,Args&... args){
        read(x);
        read(args...);
    }
    template<typename T>
    void print(T x){
        if(x<0){
            putchar('-');x=-x;
        }
        if(x==0)return;
        print(x/10);
        putchar(x%10+'0');
    }
    template<typename T,typename ...Args>
    void print(T x,Args... args){
        if(x==0){
            putchar('0');
        }
        else{
            if(x<0){
                putchar('-');
                x=-x;
            }
            print(x);           
        }
        putchar(' ');
        print(args...);
    }
}
using namespace lcy;
int a[100001];
int n,m,p;
int tree[4000001];
int qw(int x,int y,int p){
    if(y==0)return 1;
    int res=qw(x,y/2,p);
    res=res*res%p;
    if(y&1)res=res*x%p;
    return res;
}
void pushdown(int rt){
    tree[rt<<1]+=tree[rt];
    tree[rt<<1|1]+=tree[rt];
    tree[rt]=0;
    return;
}
void modify(int rt,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        tree[rt]++;
        return;
    }
    pushdown(rt);
    int mid=l+r>>1;
    if(mid>=x)modify(rt<<1,l,mid,x,y);
    if(mid<y)modify(rt<<1|1,mid+1,r,x,y);
}
int phi,lim;
int sch(int rt,int l,int r,int x){
    if(l==r){
        int ss;//拓展欧拉定理
        if(tree[rt]>=lim){
            ss=qw(3,tree[rt],phi)+phi;
        }
        else ss=qw(3,tree[rt],p);
        tree[rt]=0;
        return qw(a[x],ss,p);
    }
    int mid=l+r>>1;
    pushdown(rt);
    if(mid>=x)return sch(rt<<1,l,mid,x);
    else return sch(rt<<1|1,mid+1,r,x);
}
int mid;
unordered_map<int,int>b;
bool res;
void dfs1(int x,int sum,bool flag){//折半搜索
    if(x>mid){
        if(sum<0)return;
        if(!flag)return;
        if(sum==0)res=1;
        else b[sum]=1;
        return ;
    }
    dfs1(x+1,sum,flag);
    if(res)return;
    dfs1(x+1,sum+a[x]+1,1);
    if(res)return;
    dfs1(x+1,sum-a[x]-1,1);
}
void dfs2(int x,int sum,bool flag,int y){
    if(x>y){
        if(sum<0)return;
        if(!flag)return;
        if(sum==0)res=1;
        else if(b[sum]==1)res=1;
        return;
    }
    dfs2(x+1,sum,flag,y);
    if(res)return;
    dfs2(x+1,sum+a[x]+1,1,y);
    if(res)return;
    dfs2(x+1,sum-a[x]-1,1,y);
}
int main(){
//  freopen("1.in","r",stdin);
//  freopen("1.out","w",stdout);
    read(n,m,p);int pp=p;phi=1;
    for(int i=2;i<=sqrt(p);i++){
        if(pp%i==0){
            pp/=i;
            phi*=i-1;
        }
        while(pp%i==0){
            pp/=i;
            phi*=i;
        }
    }//预处理欧拉函数
    if(pp>1)phi*=pp-1;
    int tmp=1;
    while(tmp<=phi){
        tmp*=3;lim++;
    }
    for(int i=1;i<=n;i++)read(a[i]),a[i]%=p;
    for(int i=1;i<=m;i++){
        int op,x,y;
        read(op,x,y);
        if(op==1){
            b.clear();
            if(y-x+1>13){
                printf("Yuno\n");
                continue;
            }
            res=0;
            for(int j=x;j<=y;j++)a[j]=sch(1,1,n,j);
            mid=x+y>>1;
            dfs1(x,0,0);
            if(res){
                printf("Yuno\n");
                continue;
            }
            dfs2(mid+1,0,0,y);
            if(res)printf("Yuno\n");
            else printf("Yuki\n");
        }
        else{
            modify(1,1,n,x,y);
        }
    }
}