Emoogle Grid UVA - 11916
因为个else改了一夜，我真是个憨憨
题意：有M*N个小方格，K种颜色，B个小方格是被打碎的，然后规定除了被打碎的小方格，其他小方格都必须涂一种颜色，并且相邻上下两行不能是同一种颜色，现在给出你对1e8+7取模后的方案数R,还有N,K，B个（x,y）坐标,求最小满足要求的M。
首先最小的M肯定是大于等于被打碎的里最大的x（没有打碎的就是1），我们先不管打碎的小方格，如果全是完好的，那么根据题意第一行的可以任意涂K种颜色，然后下面受到上面的限制就都是K-1种，也就是R=KN*(K-1)(M-1)*N，
然后设q1是K的指数，q2是K-1的指数，我们考虑被打碎的小方格，如果它是第一行的，那么q1--，如果它不是最后一行的并且它下面那个小方格没被打碎，q1++，那么q2=M*N-B-q1,我们计算此时答案是不是等于R了，是的话当前的M就是答案。
而如果不是的话，那就得继续增大行数M,此时最后一行如果有打碎的小方块，那么下一行也会被影响，所以先加一行，M++,并且设最后一行打碎的小方块数目为numc，那么q1+=numc,q2+=N-numc，计算此时的答案ans，是不是等于R,如果等于答案就是M.
而如果不是的话，接下来在怎么增大M，ans都是增大(K-1)N倍，也就是解ans*(K-1)N*MMΞR (mod 1e8+7)，那很明显这就是高次同余方程，拔山盖世走起，解出MM,答案就是M+MM
1 #include<cstdio>
2 #include<map>
3 #include<cmath>
4 #include<algorithm>
5 using namespace std;
6 typedef long long ll;
7 const int N=511;
8 const ll md=1e8+7;
9 struct Node{
10 ll x,y;
11 bool operator<(const Node &n1)const{
12 return y==n1.y ? x<n1.x : y<n1.y;
13 }
14 }blo[N];
15 map<ll,ll> mmp;
16 ll rr,cc,col;
17 ll poww(ll a,ll b){
18 ll ans=1;
19 while(b){
20 if(b&1){
21 ans*=a;
22 if(ans>=md) ans%=md;
23 }
24 a*=a;
25 if(a>=md) a%=md;
26 b>>=1;
27 }
28 return ans;
29 }
30 ll solve1(int nb,ll ans){
31 ll q1=cc,q2,numc=0,res;
32 sort(blo,blo+nb);
33 for(int i=0;i<nb;i++){
34 if(blo[i].x==1) q1--;
35 if(blo[i].x==rr) numc++;
36 if(blo[i].x!=rr){
37 if(i+1<nb&&blo[i+1].y==blo[i].y&&blo[i+1].x==blo[i].x+1) continue;
38 q1++;
39 }
40 }
41 q2=rr*cc-nb-q1;
42 res=poww(col,q1)*poww(col-1,q2)%md;
43 if(res==ans) return res;
44 rr++;q1+=numc;q2+=cc-numc;
45 res=poww(col,q1)%md*poww(col-1,q2)%md;
46 return res;
47 }
48 ll bsgs(ll a,ll b,ll c,ll d){
49 int sqc=ceil(sqrt(1.0*c));
50 ll aa=1,ac=1,ab;
51 mmp.clear();
52 for(int i=0;i<sqc;i++){
53 ab=aa*b;
54 if(ab>=c) ab%=c;
55 mmp[ab]=i;
56 aa*=a;
57 if(aa>=c) aa%=c;
58 }
59 for(int i=1;i<=sqc;i++){
60 ac*=aa;
61 if(ac>=c) ac%=c;
62 ab=ac*d;
63 if(ab>=c) ab%=c;
64 if(mmp.count(ab)) return 1ll*i*sqc-mmp[ab];
65 }
66 return -1;
67 }
68 int main(){
69 int t=1,T,nb;
70 ll ans,ans1;
71 scanf("%d",&T);
72 while(t<=T){
73 rr=1;
74 scanf("%lld%lld%d%lld",&cc,&col,&nb,&ans);
75 for(int i=0;i<nb;i++){
76 scanf("%lld%lld",&blo[i].x,&blo[i].y);
77 rr=max(rr,blo[i].x);
78 }
79 printf("Case %d: ",t++);
80 ans1=solve1(nb,ans);
81 if(ans1==ans) printf("%lld\n",rr);
82 else printf("%lld\n",rr+bsgs(poww(col-1,cc),ans,md,ans1));
83 }
84 return 0;
85 }