UVA 11916 Emoogle Grid 离散对数 大步小步算法

时间：2022-08-17 05:17:32

LRJ白书上的题

#include <stdio.h>

#include <iostream>

#include <vector>

#include <math.h>

#include <set>

#include <map>

#include <queue>

#include <algorithm>

#include <string.h>

#include <string>

using namespace std;

typedef long long LL;

const LL mod=1e8+;

const int N=;

LL n,m,k,b,r,x[N],y[N];

set<pair<LL,LL> >bset;

void exgcd(LL a,LL b,LL& d,LL &x,LL &y){

    if(!b){d=a;x=;y=;}

    else {exgcd(b,a%b,d,y,x);y-=x*(a/b);}

}

LL pow_mod(LL a,LL p){

    LL ans=;

    while(p){

        if(p&)ans=(ans*a)%mod;

        p/=;

        a=(a*a)%mod;

    }

    return ans;

}

LL inv(LL a){

    LL d,x,y;

    exgcd(a,mod,d,x,y);

    return d==?(x+mod)%mod:-;

}

LL log_mod(LL a,LL b){

    LL tmp,v,e=;

    tmp=(LL)sqrt(mod+0.5);

    v=inv(pow_mod(a,tmp));

    map<LL,LL>mp;

    mp.clear();

    mp[]=;

    for(LL i=;i<tmp;++i){

        e=(e*a)%mod;

        if(!mp.count(e))mp[e]=i;

    }

    for(LL i=;i<tmp;++i){

        if(mp.count(b))return i*tmp+mp[b];

        b=(b*v)%mod;

    }

    return -;

}

LL count(){

    LL c=;

    for(LL i=;i<b;++i)

     if(x[i]!=m&&!bset.count(make_pair(x[i]+,y[i])))++c;

    c+=n;

    for(LL i=;i<b;++i)if(x[i]==)--c;

    return pow_mod(k,c)*pow_mod((k-),n*m-b-c)%mod;

}

LL solve(){

    LL cnt=count();

    if(cnt==r)return m;

    LL c=;

    for(LL i=;i<b;++i)if(x[i]==m)++c;

    ++m;

    cnt=(cnt*pow_mod(k,c))%mod;

    cnt=(cnt*pow_mod(k-,n-c))%mod;

    if(cnt==r)return m;

    return log_mod(pow_mod(k-,n),(r*inv(cnt))%mod)+m;

}

int main()

{

    int T;

    scanf("%d",&T);

    for(int t=;t<=T;++t){

        scanf("%lld%lld%lld%lld",&n,&k,&b,&r);

        bset.clear();

        m=;

        for(LL i=;i<b;++i){

            scanf("%lld%lld",&x[i],&y[i]);

            m=max(m,x[i]);

            bset.insert(make_pair(x[i],y[i]));

        }

        printf("Case %d: %lld\n",t,solve());

    }

    return ;

}

相关文章