记录编号	160154	评测结果	AAAAAAAAATTTTAT
题目名称	牛跳房子	最终得分	66
用户昵称	Chenyao2333	是否通过	未通过
代码语言	C++	运行时间	8.816 s
提交时间	2015-04-24 12:10:57	内存使用	219.75 MiB

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

const int L_N=750+2;
const int TL=100;
const int MOD=1000000007;

struct CNT{
	int k,num;
	bool operator < (const CNT & c)const{
		return num>c.num;
	}
}cs[L_N*L_N];
vector<PII> gk[L_N*L_N];

int tl[L_N*L_N],tn;
int N,M,K,gird[L_N][L_N];

struct TreeArr{
	int a[L_N][L_N];
	int lowbit(int i){ return i&-i; }
	void add(int x,int y,int val){
		val%=MOD;
		for(int i=x;i<L_N;i+=lowbit(i)){
			for(int j=y;j<L_N;j+=lowbit(j)){
				a[i][j]+=val;
				if(a[i][j]>=MOD) a[i][j]-=MOD;
			}
		}
	}
	int query(int x,int y){
		int ret=0;
		for(int i=x;i;i-=lowbit(i)){
			for(int j=y;j;j-=lowbit(j)){
				ret+=a[i][j];
				if(ret>=MOD) ret-=MOD;
			}
		}
		return ret;
	}
}ts[TL],tf;

int f[L_N][L_N];

void insert(int i,int j){
	int k=gird[i][j];
	if(tl[k]){
		ts[tl[k]].add(i,j,f[i][j]);
	}
	tf.add(i,j,f[i][j]);
}

int main(){
	freopen("hopscotch.in","r",stdin);
	freopen("hopscotch.out","w",stdout);
	
	scanf("%d %d %d",&N,&M,&K);
	
	for(int i=1;i<=K;i++) cs[i].k=i;
	
	for(int i=1;i<=N;i++) for(int j=1;j<=M;j++){
		int k; scanf("%d",&k);
		gird[i][j]=k;
		gk[k].push_back(PII(i,j));
		cs[k].num++;
	}
	
	sort(cs+1,cs+1+K);
	for(int i=1;i<=K && i<TL;i++){
		tn=i;
		tl[cs[i].k]=tn;
	}
	
	f[1][1]=1;
	insert(1,1);
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++){
			if(i==j && i==1){
				continue;
			}
			
			int tmp=tf.query(i-1,j-1);
			
			int k=gird[i][j];
			if(tl[k]){
				tmp=tmp+MOD-ts[tl[k]].query(i-1,j-1);
				if(tmp>=MOD) tmp-=MOD;
			}else{
				for(int t=0;t<gk[k].size();t++){
					int x=gk[k][t].first;
					int y=gk[k][t].second;
					if(x<i && y<j){
						tmp=tmp+MOD-f[x][y];
						if(tmp>=MOD) tmp-=MOD;
					}
				}
			}
			
			f[i][j]=tmp;
			insert(i,j);
		}
	}
	
	int ans=f[N][M];
	printf("%d\n",ans);
	return 0;
}