题意：一个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)）；
1 #include<stdio.h> 2 #include<algorithm> 3 #include<stdlib.h> 4 #include<iostream> 5 #include<queue> 6 #include<math.h> 7 #include<map> 8 #include<vector> 9 #include<string.h> 10 #include<set> 11 typedef long long LL; 12 using namespace std; 13 typedef struct pp { 14 int x; 15 int y; 16 } ss; 17 ss ans[100005]; 18 ss bns[100005]; 19 set<pair<int,int> >vec; 20 const LL mod = 100000007; 21 bool cmp(pp p, pp q) { 22 if(p.x == q .x) 23 return p.y < q.y; 24 return p.x < q.x; 25 } 26 LL coutt(int m,int n,int b,int k); 27 LL quick(LL n, LL m); 28 LL solve(int n,int m,int b,int k,int r); 29 LL BSS(LL kk,LL k,LL cnt,LL n); 30 int er(int n,int m,LL fin); 31 ss cn[100005]; 32 int main(void) { 33 int T; 34 int __ca = 0; 35 scanf("%d",&T); 36 while(T--) { 37 __ca++; 38 int n, k, b,r; 39 vec.clear(); 40 scanf("%d %d %d %d",&n,&k,&b,&r); 41 int i,j; 42 int m = 1; 43 for(i = 0 ; i < b; i++) { 44 scanf("%d %d",&ans[i].x,&ans[i].y); 45 if(ans[i].x > m)m = ans[i].x; 46 pair<int,int>ac = make_pair(ans[i].x,ans[i].y); 47 // printf("%d %d\n",ans[i].x,ans[i].y); 48 vec.insert(ac); 49 } 50 printf("Case %d: %lld\n",__ca,solve(n,m,b,k,r)); 51 } 52 return 0; 53 } 54 LL coutt(int m,int n,int b,int k) { 55 LL sum = 0; 56 for(int i = 0; i < b; i++) { //printf("%d\n",ans[i].x); 57 if(ans[i].x != m&& !vec.count(make_pair(ans[i].x+1,ans[i].y))) 58 sum++; 59 if(ans[i].x == 1) { 60 sum--; 61 } 62 } 63 sum += n; 64 LL dt = quick((LL)k,sum)%mod; 65 dt = dt*quick((LL)(k-1),(LL)m*(LL)n-b-sum)%mod; 66 return dt % mod; 67 } 68 LL quick(LL n, LL m) { 69 LL ask = 1; 70 n %= mod; 71 while(m) { 72 if(m&1) 73 ask = ask*n %mod; 74 n = n*n %mod; 75 m>>=1; 76 } 77 return ask ; 78 } 79 LL solve(int n,int m,int b,int k,int r) { 80 LL cnt = coutt(m,n,b,k); 81 if(cnt == r) 82 return (LL)m; 83 int i,j; 84 int ac = 0; 85 for(i = 0; i < b; i++) { 86 if(ans[i].x == m) { 87 ac++ ; 88 } 89 } 90 //printf("%lld\n",cnt); 91 m++; 92 LL ak = quick((LL)k,ac); 93 cnt = cnt *ak %mod; 94 ak = quick((LL)(k-1),n-ac); 95 cnt = cnt *ak%mod; 96 if(cnt == r) 97 return (LL)m; 98 LL tp = quick((LL)(k-1),n); 99 LL kk = (LL)r; 100 return (m+BSS(kk,(LL)k,cnt,n))%mod; 101 } 102 LL BSS(LL kk,LL k,LL cnt,LL n) { 103 int i,j; 104 LL ni = quick(cnt,mod-2); 105 kk = kk*ni%mod; 106 LL ak = quick(k-1,n)%mod; 107 LL modd = sqrt(1.0*mod); 108 LL ac = kk; 109 LL nii = quick(ak,mod-2); 110 for(i = 0; i < modd; i++) { 111 bns[i].x = ac; 112 bns[i].y = i; 113 ac = ac*nii%mod; 114 } 115 116 sort(bns,bns+modd,cmp); 117 int cnn = 1; 118 cn[0] = bns[0]; 119 int c = bns[0].x; 120 for(i = 1; i <modd; i++) { 121 if(c!=bns[i].x) { 122 c=bns[i].x; 123 cn[cnn]=bns[i]; 124 cnn++; 125 } 126 } 127 LL akk = 1; 128 LL app = quick(ak,modd); 129 for(i = 0; i <= modd+1; i++) { 130 int ack = er(0,cnn,akk); 131 if(ack!=-1) { //printf("%d %lld\n",i,ack); 132 return modd*(LL)i+(LL)ack; 133 } 134 akk = akk*app%mod; 135 } 136 } 137 int er(int n,int m,LL fin) { 138 if(n>m) 139 return -1; 140 int mid = (n+m)/2; 141 if(cn[mid].x == fin) { 142 return cn[mid].y; 143 } else if(cn[mid].x > fin) { 144 return er(n,mid-1,fin); 145 } else return er(mid+1,m,fin); 146 }