ICPC2019南京网络赛

B.super_log

Problem

求a^aa...总共b个a，结果%m

Solution

欧拉降幂

Code

#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
#define inf 0x7fffffffffffffff
#define mem(a, x) memset(a,x,sizeof(a))
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef std::pair<int, int> Pii;
typedef std::pair<ll, ll> Pll;
ll power(ll a, ll b,ll p) { ll res = 1; for (; b > 0; b >>= 1) { if (b & 1) res = res * a % p; a = a * a % p; } return res; }
ll gcd(ll p, ll q) { return q == 0 ? p : gcd(q, p % q); }
ll _abs(ll x){return x < 0 ? -x : x;}
using namespace std;
const int maxn=1000000;
bool check[maxn+10];
int phi[maxn+10];
int prime[maxn+10];
int tot;//素数的个数
void phi_and_prime_table(int N)//1~n以内的所有素数  已经欧拉函数
{
    memset(check,false,sizeof(check));
    phi[1]=1;
    tot=0;
    for(int i=2;i<=N;++i)
    {
        if(!check[i])
        {
            prime[tot++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<tot;++j)
        {
            if(i*prime[j]>N) break;
            check[i*prime[j]]=true;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
            {
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
}
ll quick_pow(ll a,ll b,ll mod)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans%mod;
}
ll lowspeed(ll a,ll b,ll p){
    ll cur=a,ans=0;
    while(b){
        if(b&1) ans=(ans+cur)%p;
        cur=(cur+cur)%p;
        b>>=1;
    }
    return ans%p;
}
ll speed(ll a,ll b,ll p){
    ll cur=a,ans=1;
    while(b){
        if(b&1) ans=lowspeed(ans,cur,p)%p;
        cur=lowspeed(cur,cur,p)%p;
        b>>=1;
    }
    return ans%p;
}
ll my_pow(ll a,ll b){
    ll ans=1;
    while(b)
    {
        if(b&1) ans=(ans*a);
        if(ans>1e6) return ans;
        a=(a*a);
        if(a>1e6) return a;
        b>>=1;
    }
    return ans;
}
int T,n;
ll a,b,m,p,ans;
ll fun(ll x,ll las){
    if(las==1){
        return 0;
    }
    if(x==0){
        return 1;
    }
    if(gcd(las,a)==1){
        return speed(a,fun(x-1,phi[las])%phi[las],las);
    }
    else{
        ll anss=1;
        for(int i=1;i<=x-1;i++){
            anss=my_pow(a,anss);
            if(anss>=phi[las]){
                return speed(a,fun(x-1,phi[las])%phi[las]+phi[las],las);
            }
        }
        return speed(a,anss,las);
    }

}
int main(){
    //cout<<quick_pow(6,46656,600);
    phi_and_prime_table(1000000);
    io_opt;
    cin>>T;
    while(T--){
        cin>>a>>b>>m;
        cout<<fun(b,m)<<endl;
    }
    return 0;
}

F.Greedy Sequence

Problem

每次求区间小于i的最大值。

Solution

每次添加小于i的数，线段树查询。

Code

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<cstring>
#include<algorithm>
#define ll long long
#define inf 0x7fffffffffffffff
using namespace std;
const int N = 1e5+10;
struct B
{
    int l,r,max;
} tree[N*4];

int num[N];
int a[N],b[N];
int pos[N];
int P;

const int MAX_N=1<<17;//1e5
const int INT_MINN=-1;
int n,dat[2*MAX_N-1],x,y;
void update(int k,int a){
    k+=n-1;
    dat[k]=a;
    while(k>0){
        k=(k-1)/2;
        dat[k]=max(dat[k*2+1],dat[k*2+2]);
    }
}
void init(int n_){
    n=1;
    while(n<n_){
        n*=2;
    }
    for(int i=0;i<2*n-1;i++){
        dat[i]=INT_MINN;
    }
    for(int i=0;i<n_;i++){
        x=0;
        update(i,x);
    }
}

int query(int a,int b,int k,int l,int r){
    if(r<=a||b<=l){
        return INT_MINN;
    }
    if(a<=l&&r<=b){
        return dat[k];
    }
    else{
        int vl=query(a,b,k*2+1,l,(l+r)/2);
        int vr=query(a,b,k*2+2,(l+r)/2,r);
        return max(vl,vr);
    }
}
struct E{
    int a,pla;
}e[100020];
int yyn;
int cmp(E x,E y){
    return x.a<y.a;
}
int main()
{
    int t;
    int k;
    cin>>t;
    while (t--)
    {
        int i,j;
        int ans[N];
        P=0;
        memset(ans,0,sizeof(ans));

        cin>>n>>k;
        yyn=n;
        //cout<<yyn<<endl;
        init(n);
        for(int i=0;i<yyn;i++){
            scanf("%d",&e[i].a);
            e[i].pla=i;
            pos[e[i].a]=i;
        }
        sort(e,e+yyn,cmp);
        ans[1]=1;
        for (i=2;i<=yyn;i++)
        {

            int maxx=0;
            update(e[i-2].pla,e[i-2].a);
            maxx=query(pos[i]-k,pos[i]+k+1,0,0,n); //查询小于i的最大值
            ans[i]+=ans[maxx];
            ans[i]++;
        }

        for (i=1;i<=yyn-1;i++)
            cout<<ans[i]<<' ';
        cout<<ans[yyn]<<endl;
    }

    return 0;

}