(UVA)11916 Emoogle Grid-程序员宅基地

题意：一个N列的网格，有B个格子可以不涂色，其他格子各涂一种颜色，现在一共有k种颜色，要求同一列格子颜色不能相同，问总方案数 MOD 100000007答案等于R时最小的M是多少。

思路：首先这个m一定是大于等于所给的不能放的点的x的最大值。我们可以先统计出当前矩阵的方案数，我们知道如果当前格子上面能放东西，当前格子的方案数是k-1,否则就是k种，然后乘法原理，所以先判断下当前的m是否符合，然后不符合的情况下，再加一层，再判断下，算出当前答案cnt，你再往下加层数的时候情况是一样的，都是cnt*(（k-1）^n);然后就转换成

求cnt*(（k-1）^(n*t))%mod = r;然后大步小步算出t的最小值再加上原来m就是答案，复杂度（sqrt(mod)）；

#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#include<iostream>
#include<queue>
#include<math.h>
#include<map>
#include<vector>
#include<string.h>
#include<set>
typedef long long LL;
using namespace std;
typedef struct pp {
        int x;
        int y;
} ss;
ss ans[100005];
ss bns[100005];
set<pair<int,int> >vec;
const  LL mod = 100000007;
bool cmp(pp p, pp q) {
        if(p.x == q .x)
                return p.y < q.y;
        return p.x < q.x;
}
LL coutt(int m,int n,int b,int k);
LL quick(LL n, LL m);
LL solve(int n,int m,int b,int k,int r);
LL BSS(LL kk,LL k,LL cnt,LL n);
int er(int n,int m,LL fin);
ss cn[100005];
int main(void) {
        int T;
        int __ca = 0;
        scanf("%d",&T);
        while(T--) {
                __ca++;
                int  n, k, b,r;
                vec.clear();
                scanf("%d %d %d %d",&n,&k,&b,&r);
                int i,j;
                int  m = 1;
                for(i = 0 ; i  < b; i++) {
                        scanf("%d %d",&ans[i].x,&ans[i].y);
                        if(ans[i].x > m)m = ans[i].x;
                        pair<int,int>ac = make_pair(ans[i].x,ans[i].y);
                        // printf("%d %d\n",ans[i].x,ans[i].y);
                        vec.insert(ac);
                }
                printf("Case %d: %lld\n",__ca,solve(n,m,b,k,r));
        }
        return 0;
}
LL coutt(int m,int n,int b,int k) {
        LL sum = 0;
        for(int i = 0; i < b; i++) {
    //printf("%d\n",ans[i].x);
                if(ans[i].x != m&& !vec.count(make_pair(ans[i].x+1,ans[i].y)))
                        sum++;
                if(ans[i].x == 1) {
                        sum--;
                }
        }
        sum += n;
        LL dt = quick((LL)k,sum)%mod;
        dt =  dt*quick((LL)(k-1),(LL)m*(LL)n-b-sum)%mod;
        return dt % mod;
}
LL quick(LL n, LL m) {
        LL ask = 1;
        n %= mod;
        while(m) {
                if(m&1)
                        ask =  ask*n %mod;
                n = n*n %mod;
                m>>=1;
        }
        return ask ;
}
LL solve(int n,int m,int b,int k,int r) {
        LL cnt = coutt(m,n,b,k);
        if(cnt == r)
                return (LL)m;
        int i,j;
        int ac = 0;
        for(i = 0; i < b; i++) {
                if(ans[i].x == m) {
                        ac++ ;
                }
        }
        //printf("%lld\n",cnt);
        m++;
        LL ak = quick((LL)k,ac);
        cnt = cnt *ak %mod;
        ak = quick((LL)(k-1),n-ac);
        cnt = cnt *ak%mod;
        if(cnt == r)
                return (LL)m;
        LL tp = quick((LL)(k-1),n);
        LL kk = (LL)r;
        return (m+BSS(kk,(LL)k,cnt,n))%mod;
}
LL BSS(LL kk,LL k,LL cnt,LL n) {
        int i,j;
        LL ni = quick(cnt,mod-2);
        kk = kk*ni%mod;
        LL ak = quick(k-1,n)%mod;
        LL modd = sqrt(1.0*mod);
        LL ac = kk;
        LL nii = quick(ak,mod-2);
        for(i = 0; i < modd; i++) {
                bns[i].x = ac;
                bns[i].y = i;
                ac = ac*nii%mod;
        }

        sort(bns,bns+modd,cmp);
        int cnn = 1;
        cn[0] = bns[0];
        int c = bns[0].x;
        for(i = 1; i <modd; i++) {
                if(c!=bns[i].x) {
                        c=bns[i].x;
                        cn[cnn]=bns[i];
                        cnn++;
                }
        }
        LL akk = 1;
        LL app = quick(ak,modd);
        for(i = 0; i <= modd+1; i++) {
                int ack = er(0,cnn,akk);
                if(ack!=-1) {   //printf("%d %lld\n",i,ack);
                        return modd*(LL)i+(LL)ack;
                }
                akk = akk*app%mod;
        }
}
int er(int n,int m,LL fin) {
        if(n>m)
                return -1;
        int mid = (n+m)/2;
        if(cn[mid].x == fin) {
                return cn[mid].y;
        } else if(cn[mid].x > fin) {
                return er(n,mid-1,fin);
        } else return er(mid+1,m,fin);
}