[uva11916] Emoogle Grid (离散对数)

转载请注明出处： http://www.cnblogs.com/fraud/ ——by fraud

Emoogle Grid

You have to color an MxN ( 1M, N10⁸) two dimensional grid. You will be provided K ( 2K10⁸) different colors to do so. You will also be provided a list of B ( 0B500) list of blocked cells of this grid. You cannot color those blocked cells. A cell can be described as (x, y), which points to the y-th cell from the left of the x-th row from the top.

While coloring the grid, you have to follow these rules -

You have to color each cell which is not blocked.
You cannot color a blocked cell.
You can choose exactly one color from K given colors to color a cell.
No two vertically adjacent cells can have the same color, i.e. cell (x, y) and cell (x + 1, y) cannot contain the same color.

Now the great problem setter smiled with emotion and thought that he would ask the contestants to find how many ways the board can be colored. Since the number can be very large and he doesn't want the contestants to be in trouble dealing with big integers; he decided to ask them to find the result modulo 100,000,007. So he prepared the judge data for the problem using a random generator and saved this problem for a future contest as a giveaway (easiest) problem.

But unfortunately he got married and forgot the problem completely. After some days he rediscovered his problem and became very excited. But after a while, he saw that, in the judge data, he forgot to add the integer which supposed to be the `number of rows'. He didn't find the input generator and his codes, but luckily he has the input file and the correct answer file. So, he asks your help to regenerate the data. Yes, you are given the input file which contains all the information except the `number of rows' and the answer file; you have to find the number of rows he might have used for this problem.

Input

Input starts with an integer T ( T150), denoting the number of test cases.

Each test case starts with a line containing four integers N, K, B and R ( 0R < 100000007) which denotes the result for this case. Each of the next B lines will contains two integers x and y ( 1xM, 1yN), denoting the row and column number of a blocked cell. All the cells will be distinct.

Output

For each case, print the case number and the minimum possible value of M. You can assume that solution exists for each case.

Sample Input

4
3 3 0 1728
4 4 2 186624
3 1
3 3
2 5 2 20
1 2
2 2
2 3 0 989323

Sample Output

Case 1: 3
Case 2: 3
Case 3: 2
Case 4: 20

题意：有M行N列的网格，给其涂上K中颜色，其中有B个已知位置的格子不能涂颜色，要求上下两个相邻的格子的颜色不能相同，问在方案数mod100,000,007=R的情况下，M为多少？（保证已知位置的格子一定在M行N列内）保证M有解

分析：所有在第一行或者其上方的格子为不可涂时的格子的涂色方案数为K，其余点的涂色方案数为K-1.

设所有已知位置的格子的行的最大值为x，记在前x-1行内不可涂色的格子相邻的下方的可涂色格子的数目为a,不可涂色的格子中位于第一行的格子的数目为b，则最终可涂K种颜色的格子的数目为a+N-b，只能涂K-1中颜色的格子的数目为x*N-(a+N-b);则求x行的涂色方案为temp=K^(a+N-b)*(K-1)^(x*N-(a+N-b)),若temp=R,则temp即为答案

再考虑第x+1行的情况，若第x行为不可涂色的格子，则这一行的其下方相邻的格子的涂色方案为K,否则为K-1，记可涂K-1种的数目为c，则temp=temp*K^c*(K-1)^(N-c)，若temp=R，则temp即为答案

则接下来的每行的新的涂色方案数都为cnt=(K-1)^N,即接下来求cnt^ans*temp=R(mod100,000,007)

cnt^ans=temp^-1*R(mod100,000,007)

然后求一下离散对数即可

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <algorithm>
  5 #include <cmath>
  6 #include <set>
  7 #define X first
  8 #define Y second
  9 #include <map>
 10 using namespace std;
 11 
 12 typedef pair<int,int> PII;
 13 typedef long long ll;
 14 ll n,k,b,r;
 15 set<PII> s;
 16 PII p[1010];
 17 ll maxx=0;
 18 const int mod=100000007;
 19 ll mul_mod(ll x,ll y)
 20 {
 21     return (ll)x*y%mod;
 22 }
 23 ll fast_mod(int m,ll t)
 24 {
 25     ll temp=(long long)m;
 26     ll ret=1LL;
 27     while(t)
 28     {
 29         if(t&1)ret=mul_mod(ret,temp);
 30         temp=mul_mod(temp,temp);
 31         t/=2;
 32     }
 33     return ret;
 34 }
 35 ll ext_gcd(ll a,ll t,ll &d,ll &x,ll &y)
 36 {
 37     if(!t){d=a;x=1;y=0;}
 38     else {
 39         ext_gcd(t,a%t,d,y,x);y-=x*(a/t);
 40     }
 41 }
 42 ll inv(ll a)
 43 {
 44     ll d,x,y;
 45     ext_gcd(a,mod,d,x,y);
 46     return d == 1 ? (x%mod+mod)%mod : -1;
 47 }
 48 ll log_mod(ll a,ll b)
 49 {
 50     ll m,v,e=1,i;
 51     m=(ll)sqrt(mod+0.5);
 52     v=inv(fast_mod(a,m));
 53     map<ll ,ll >x;
 54     x.clear();
 55     x[1]=0;
 56     for(i=1;i<m;i++)
 57     {
 58         e=mul_mod(e,a);
 59         if(!x.count(e))x[e]=i;
 60     }
 61     for(i=0;i<m;i++)
 62     {
 63         if(x.count(b))return i*m+x[b];
 64         b=mul_mod(b,v);
 65     }
 66     return -1;
 67 }
 68 ll solve()
 69 {
 70     int temp=0;
 71     for(int i=0;i<b;i++)
 72         if(p[i].X!=maxx&&!s.count(make_pair(p[i].X+1,p[i].Y)))temp++;
 73     temp+=n;
 74     for(int i=0;i<b;i++)
 75         if(p[i].X==1)temp--;
 76     ll ret=mul_mod(fast_mod(k,temp),fast_mod(k-1,(long long)maxx*n-b-temp));
 77     if(ret==r)return maxx;
 78     temp=0;
 79     for(int i=0;i<b;i++)if(p[i].X==maxx)temp++;
 80     maxx++;
 81     ret=mul_mod(ret,fast_mod(k,temp));
 82     ret=mul_mod(ret,fast_mod(k-1,n-temp));
 83     if(ret==r)return maxx;
 84     //求(ret*((k-1)^n)^x)%mod=r
 85     //即((k-1)^n)^x=r*(ret^(-1))%mod
 86     return log_mod(fast_mod(k-1,n),mul_mod(r,inv(ret)))+maxx;
 87 }
 88 
 89 int main()
 90 {
 91     ios::sync_with_stdio(false);
 92     int t;
 93     //freopen("in.in","r",stdin);
 94     cin>>t;
 95     int cas=1;
 96     while(t--)
 97     {
 98         maxx=1;
 99         s.clear();
100         cin>>n>>k>>b>>r;
101         for(int i=0;i<b;i++)
102         {
103             cin>>p[i].X>>p[i].Y;
104             if(p[i].X>maxx)maxx=p[i].X;
105             s.insert(p[i]);
106         }
107         cout<<"Case "<<cas++<<": "<<solve()<<endl;
108     }
109     return 0;
110 }

代码君