记录编号	88162	评测结果	AAAAAAAAAA
题目名称	[UVa 11741] 网格覆盖	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.981 s
提交时间	2014-02-17 20:18:00	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<deque>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
//本题下标从0开始
ll MOD=10000007;
const int SIZES=16,SIZER=4;
int R,C,N;
vector<pair<int,int> > unusable;//first是列坐标,second是行坐标
void printdig(int x){//调试接口,以二进制形式输出x
	for(int i=R-1;i>=0;i--){cout<<((x>>i)&1);}
}
class MATRIX{
public:
	int n,m;
	ll s[SIZES][SIZES];
	void clear(int x,int y){
		n=x,m=y;
		memset(s,0,sizeof(s));
	}
	void assign_one(int x){
		clear(x,x);
		for(int i=0;i<x;i++) s[i][i]=1;
	}
	void print(void){//调试接口,输出转移矩阵的情况
		cout<<"size:"<<n<<" "<<m<<endl;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){if(s[i][j]==0){continue;}printdig(i);cout<<" ";printdig(j);cout<<" :"<<s[i][j]<<endl;}
		}
	}
};
inline MATRIX operator * (MATRIX &a,MATRIX &b){
	MATRIX ans;
	ans.clear(a.n,b.m);
	for(int i=0;i<a.n;i++){
		for(int j=0;j<b.m;j++){
			for(int k=0;k<a.m;k++){
				ans.s[i][j]+=(a.s[i][k]*b.s[k][j])%MOD;
				//ans.s[i][j]%=MOD;
			}
			ans.s[i][j]%=MOD;
		}
	}
	return ans;
}
inline MATRIX quickpow(MATRIX a,int n){
	MATRIX ans;
	ans.assign_one(a.n);
	while(n){
		if(n&1) ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
MATRIX nD;//全白列的转移矩阵
vector<pair<int,MATRIX> > cD;//第first列的转移矩阵
bool cv[SIZER];
void DFS(MATRIX &D,int s1,int s2,int p){
	if(p>R) return;
	if(p==R){
		D.s[s1][s2]++;
		return;
	}
	if(cv[p]){
		DFS(D,s1*2+1,s2*2+1,p+1);
		return;
	}
	DFS(D,s1*2,s2*2+1,p+1);//这一格不放
	DFS(D,s1*2+1,s2*2,p+1);//竖着放
	if(p<R-1&&!cv[p+1]) DFS(D,s1*4+3,s2*4+3,p+2);//横着放
}
void prepare(void){
	int i=0,j,k;
	MATRIX nowd;
	nD.clear(1<<R,1<<R);
	memset(cv,0,sizeof(cv));
	DFS(nD,0,0,0);
	while(i<unusable.size()){
		j=i+1;
		while(j<unusable.size()&&unusable[j].first==unusable[i].first) j++;
		memset(cv,0,sizeof(cv));
		nowd.clear(1<<R,1<<R);
		for(k=i;k<j;k++) cv[unusable[k].second]=true;
		DFS(nowd,0,0,0);
		cD.push_back(make_pair(unusable[i].first,nowd));
		i=j;
	}
}
int kase=0;
void work(){
	prepare();
	MATRIX ori;
	ori.clear(1,1<<R);
	ori.s[0][(1<<R)-1]=1;
	int tot=-1;
	MATRIX temp;
	for(int i=0;i<cD.size();i++){
		if(cD[i].first-1-tot>0){
			temp=quickpow(nD,cD[i].first-1-tot);
			ori=ori*temp;
		}
		ori=ori*cD[i].second;
		tot=cD[i].first;
	}
	if(C-1-tot>0){
		temp=quickpow(nD,C-1-tot);
		ori=ori*temp;
	}
	printf("Case %d: %lld\n",++kase,ori.s[0][(1<<R)-1]);
}
bool init(void){
	unusable.clear();
	cD.clear();
	scanf("%d%d%d",&R,&C,&N);
	if(!R&&!C&&!N) return false;
	int x,y;
	for(int i=1;i<=N;i++){
		scanf("%d%d",&x,&y);
		unusable.push_back(make_pair(y,x));
	}
	sort(unusable.begin(),unusable.end());
	return true;
}
int main(){
	freopen("ignoretheblocks.in","r",stdin);
	freopen("ignoretheblocks.out","w",stdout);
	while(init()) work();
	return 0;
}