记录编号	409282	评测结果	AAAAAAAAAA
题目名称	[UVa 11916] 网格涂色	最终得分	100
用户昵称	nonamenotitle	是否通过	通过
代码语言	C++	运行时间	3.923 s
提交时间	2017-05-27 11:05:03	内存使用	3.17 MiB

#include <iostream>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define mem(x) memset(x,0,sizeof(x))

typedef long long ll;
const ll MOD=100000007;
ll kas,n,k,b,r,m;
ll X[500+5],Y[500+5];
set<pair<ll ,ll > > pet;
/*ll quickpow(ll x,ll k){
	if(k==0) return 1;
	//printf("x=%lld k=%lld\n",x,k);
	ll res=1;
	while(k>0){
		if(k&1) res=(ll)res*x%MOD;
		x=(ll)x*x%MOD;
		k=k/2;
	}
	//printf("res=%lld\n",res);
	return res;
}*/
ll quickpow(ll a,ll p)
{
	if(p==0) return 1;
	ll ans=quickpow(a,p/2);
	ans=(long long )ans*ans%MOD;
	if(p%2) ans=(long long )ans*a%MOD;
	return ans;
}
ll inv(ll a)
{
	return quickpow(a,MOD-2);
}
ll mul_mod(ll a,ll b)
{
	return (long long)a*b%MOD;
}
ll log_mod(ll a,ll b)
{
	ll m=(ll)sqrt(MOD);
	ll poww=quickpow(a,m);
	//printf("poww=%lld\n",poww);
	ll v=inv(poww);
	map<ll ,ll > rfl;rfl.clear();rfl[1]=0;
	//printf("v=%lld\n",v);
	ll e=1;
	for(ll i=1;i<m;i++){
		e=mul_mod(e,a);if(!rfl.count(e)) rfl[e]=i;
	}
	for(ll i=0;i<m;i++){
		if(rfl.count(b)) return rfl[b]+i*m;
		b=mul_mod(b,v);
	}
	return -1;
}
ll getcount()
{
	ll c=0;
	for(ll i=0;i<b;i++)
		if(X[i]!=m && !pet.count(make_pair(X[i]+1,Y[i]))) c++;
	c+=n;
	for(ll i=0;i<b;i++) if(X[i]==1) c--;
	ll cnt=mul_mod(quickpow(k,c),quickpow(k-1,(long long)m*n-b-c));
	//printf("cnt=%lld\n",cnt);
	return cnt;
}
ll solve()
{
	ll cnt=getcount();
	if(cnt==r) return m;
	ll c=0;
	for(ll i=0;i<b;i++)
		if(X[i]==m) c++;
	m++;
	cnt=mul_mod(cnt,quickpow(k,c));
	cnt=mul_mod(cnt,quickpow(k-1,n-c));
	if(cnt==r) return m;
	ll invv=inv(cnt);
	ll lgg=log_mod(quickpow(k-1,n),mul_mod(r,invv));
	return lgg+m;
}
int main()
{
	freopen("emoogle.in","r",stdin);
	freopen("emoogle.out","w",stdout);
 	//freopen("1.out","w",stdout);
	scanf("%lld",&kas);
	for(ll z=0;z<kas;z++)
	{
		pet.clear();m=1;
		mem(X),mem(Y);
		scanf("%lld%lld%lld%lld",&n,&k,&b,&r);
		for(ll i=0;i<b;i++){
			ll x,y;scanf("%lld%lld",&x,&y);
			X[i]=x;Y[i]=y;
			pet.insert(make_pair(x,y));
			m=max(m,x);
		}
		printf("Case %lld: %lld\n",z+1,solve());
	}
	return 0;
}