记录编号 353549 评测结果 AAAAAAAAAAAAAAA
题目名称 牛跳房子 最终得分 100
用户昵称 GravatarDrench 是否通过 通过
代码语言 C++ 运行时间 1.524 s
提交时间 2016-11-18 09:11:57 内存使用 8.92 MiB
显示代码纯文本
#include<cstdio>
const int N=752,P=1000000007;
int n,m,k,i,j,a[N][N],f[N][N],T,all,s[N*N],v[N*N];
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
void solve(int l,int r){
  if(l==r)return;
  int mid=(l+r)>>1;
  solve(l,mid);
  for(T++,all=0,j=1;j<=m;j++){
    for(i=r;i>mid;i--){
      if(v[a[i][j]]<T)v[a[i][j]]=T,s[a[i][j]]=0;
      f[i][j]=((f[i][j]+all-s[a[i][j]])%P+P)%P;
    }
    for(i=l;i<=mid;i++){
      if(v[a[i][j]]<T)v[a[i][j]]=T,s[a[i][j]]=0;
      (s[a[i][j]]+=f[i][j])%=P,(all+=f[i][j])%=P;
    }
  }
  solve(mid+1,r);
}
int main(){
  freopen("hopscotch.in", "r", stdin);
  freopen("hopscotch.out", "w", stdout);
  read(n),read(m),read(k);
  for(i=f[1][1]=1;i<=n;i++)for(j=1;j<=m;j++)read(a[i][j]);
  solve(1,n);
  return printf("%d",f[n][m]),0;
}