记录编号	85809	评测结果	AAAAAAAAAA
题目名称	[UVa 11916] 网格涂色	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	11.238 s
提交时间	2014-01-13 13:49:51	内存使用	3.16 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<iomanip>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
const ll MOD=100000007;
ll quickpow(ll a,ll n){
	ll ans=1;
	while(n){
		if(n&1) ans=(ans*a)%MOD;
		a=(a*a)%MOD;
		n>>=1;
	}
	return ans;
}
void extend_gcd(ll a,ll b,ll &x,ll &y,ll &d){
	if(b==0){d=a;x=1;y=0;}
	else{extend_gcd(b,a%b,y,x,d);y-=(a/b)*x;}
}
ll inverse(ll a){//a对模MOD的逆元,无解返回-1
	ll x,y,d;
	extend_gcd(a,MOD,x,y,d);
	return d==1?(x+MOD)%MOD:-1;//这个+不可少,因为x可能为负数
}
ll dclog(ll a,ll b){//求解方程:a^x=b(模 MOD),返回最小解,无解返回-1
	//采用大步小步法
	map<ll,ll> base;
	ll m=(ll)sqrt(MOD+0.5),e=1,i,v;
	v=inverse(quickpow(a,m));
	base[1]=0;
	for(i=1;i<m;i++){
		e=(e*a)%MOD;
		if(!base.count(e)) base[e]=i;
	}
	for(i=0;i<=MOD/m;i++){
		if(base.count(b)) return (i*m+base[b])%(MOD-1);
		b=(b*v)%MOD;
	}
	return -1;
}
const ll SIZEB=510;
ll N,K,B,R,M;//M是不变部分的行数
ll ivx[SIZEB]={0},ivy[SIZEB]={0};//无效格子的列表
set<pair<ll,ll> > invalid;//无效的格子
ll imb_count(void){//不变部分总共有多少种放法
	ll cnt1=0,cnt2=0;//cnt1是上面有不可染格子的数量,cnt2是其他的
	ll i;
	for(i=1;i<=B;i++) if(ivx[i]!=M&&!invalid.count(make_pair(ivx[i]+1,ivy[i]))) cnt1++;//不可染格子下面的可染格
	cnt1+=N;//第一行格子可以随意染色
	for(i=1;i<=B;i++) if(ivx[i]==1) cnt1--;//扣除第一行的不可染色格子
	cnt2=(N*M)-B-cnt1;//只有K-1种染法的格子数量
	ll ans=quickpow(K,cnt1)*quickpow(K-1,cnt2);ans%=MOD;
	return ans;
}
ll answer(void){
	ll base=imb_count();
	if(base==R) return M;
	ll cnt=0,i,step;
	for(i=1;i<=B;i++) if(ivx[i]==M) cnt++;
	//第M+1行中,有cnt个格子是K种放法,N-cnt个格子是K-1种放法
	base=(base*quickpow(K,cnt))%MOD;
	base=(base*quickpow(K-1,N-cnt))%MOD;
	M++;
	if(base==R) return M;//不可变部分+可变部分第一行
	step=quickpow(K-1,N);
	return dclog(step,(inverse(base)*R)%MOD)+M;
}
void read(void){
	scanf("%lld%lld%lld%lld",&N,&K,&B,&R);
	invalid.clear();
	M=1;
	for(ll i=1;i<=B;i++){
		scanf("%lld%lld",&ivx[i],&ivy[i]);
		M=max(M,ivx[i]);
		invalid.insert(make_pair(ivx[i],ivy[i]));
	}
}
int main(){
	freopen("emoogle.in","r",stdin);
	freopen("emoogle.out","w",stdout);
	ll T;
	scanf("%d",&T);
	for(ll i=1;i<=T;i++){
		read();
		printf("Case %lld: %lld\n",i,answer());
	}
	return 0;
}