记录编号	154571	评测结果	AAAAAAAAAAA
题目名称	[CF 293B]不同的路径	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.274 s
提交时间	2015-03-23 10:04:20	内存使用	19.80 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const LL MOD=1000000007;
const int SIZEN=1010;
int N,M,K;
int board[SIZEN][SIZEN]={0};
LL ans=0;
int state[SIZEN][SIZEN]={0};
int lisx[SIZEN],lisy[SIZEN];//其实这个大小是不严谨的但反正够用
int tot=0;
int used[SIZEN]={0};
int now[SIZEN][SIZEN]={0};
LL fact[SIZEN]={0};
void generate_lis(void){
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++){
			lisx[tot]=i;
			lisy[tot]=j;
			tot++;
		}
	}
}
LL calc_P(int n,int m){
	if(m==0) return 1;
	LL ans=1;
	for(int i=0;i<m;i++){
		ans=ans*(n-i)%MOD;
	}
	return ans;
}
LL P[SIZEN][SIZEN]={0};
int match1[SIZEN]={0},match2[SIZEN]={0};
LL calc(void){
	for(int i=0;i<K;i++) match1[i]=match2[i]=-1;
	int indep=K,sure=0;//独立的个数
	while(!used[indep-1]) indep--;
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++){
			if(board[i][j]!=-1){
				if(match1[now[i][j]]!=-1&&match1[now[i][j]]!=board[i][j]) return 0;
				if(match2[board[i][j]]!=-1&&match2[board[i][j]]!=now[i][j]) return 0;
				if(match1[now[i][j]]==-1){
					indep--;
					sure++;
				}
				match1[now[i][j]]=board[i][j];
				match2[board[i][j]]=now[i][j];
			}
		}
	}
	return P[K-sure][indep];
}
void DFS(int p){
	if(p>=tot){
		ans+=calc();
		ans%=MOD;
		return;
	}
	int &i=lisx[p],&j=lisy[p];
	for(int k=0;k<K;k++){
		if(!used[k]){
			used[k]=true;
			int msk=1<<k;
			if(!(state[i-1][j]&msk)&&!(state[i][j-1]&msk)){
				state[i][j]=state[i-1][j]|state[i][j-1]|msk;
				now[i][j]=k;
				DFS(p+1);
			}
			used[k]=false;
			break;
		}
		else{
			int msk=1<<k;
			if(!(state[i-1][j]&msk)&&!(state[i][j-1]&msk)){
				state[i][j]=state[i-1][j]|state[i][j-1]|msk;
				now[i][j]=k;
				DFS(p+1);
			}
		}
	}
}
void work(void){
	fact[0]=1;
	for(int i=1;i<=K;i++) fact[i]=(fact[i-1]*i)%MOD;
	for(int i=0;i<=K;i++){
		for(int j=0;j<=i;j++){
			P[i][j]=calc_P(i,j);
		}
	}
	if(N+M-1>K){
		printf("0\n");
	}
	else{
		generate_lis();
		DFS(0);
		cout<<ans<<endl;
	}
}
void read(void){
	scanf("%d%d%d",&N,&M,&K);
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++){
			scanf("%d",&board[i][j]);
			board[i][j]--;
		}
	}
}
int main(){
	freopen("distinctpaths.in","r",stdin);
	freopen("distinctpaths.out","w",stdout);
	read();
	work();
	return 0;
}