Description
就像人类喜欢玩“跳房子”的游戏，农民约翰的奶牛已经发明了该游戏的一个变种自己玩。由于笨拙的动物体重近一吨打，牛跳房子几乎总是以灾难告终，但这是没有阻止奶牛几乎每天下午玩这个游戏。
游戏的矩阵共有R*C格（2 <= R <= 750，2 <= C <= 750），其中每一格是个正方形并被标记为一个整数K( 1 < = K <= R * C）。游戏是牛开始在左上角最后向右下角移动到的一个跳跃序列，牛从一个格子只能跳到在他的严格右下方(行列都要大于当前位置)与当前格子权值不同的格子上。请帮助奶牛计算不同可能的有效跳跃序列的数量。
Input
第一行三个整数 R, C, K.
以下R行，每行 C个整数.
Output
输出方案数，由于数太大，请对答案取模 1000000007.
Sample Input
4 4 4
1 1 1 1
1 3 2 1
1 2 4 1
1 1 1 1
Sample Output
5
正解：分治or线段树
对于列分治，每次分治时，先把≤mid的区间处理，再统计≤mid的答案，然后加入>mid的区间中，复杂度O(n*m log n)。
取模的话，%一波r_64大神。。
//It is made by wfj_2048~
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define inf (1<<30)
#define il inline
#define RG register
#define ll long long
#define rhl 1000000007
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) using namespace std; int a[760][760],vis[562510],n,m,k,T;
ll f[760][760],s[562510]; il int gi(){
RG int x=0,q=1; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
if (ch=='-') q=-1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x;
} il void solve(RG int l,RG int r){
if (l==r) return; RG int mid=(l+r)>>1;
solve(l,mid); T++; RG ll sum=0;
for (RG int i=2;i<=n;++i){
for (RG int j=l;j<=mid;++j){
if (vis[a[i-1][j]]!=T) s[a[i-1][j]]=0,vis[a[i-1][j]]=T;
(sum+=f[i-1][j])%=rhl,(s[a[i-1][j]]+=f[i-1][j])%=rhl;
}
for (RG int j=mid+1;j<=r;++j){
if (vis[a[i][j]]!=T) s[a[i][j]]=0,vis[a[i][j]]=T;
(f[i][j]+=sum-s[a[i][j]]+rhl)%=rhl;
}
}
solve(mid+1,r); return;
} il void work(){
n=gi(),m=gi(),k=gi(); f[1][1]=1;
for (RG int i=1;i<=n;++i)
for (RG int j=1;j<=m;++j) a[i][j]=gi();
solve(1,m); printf("%lld\n",f[n][m]); return;
} int main(){
File("cowhouse");
work();
return 0;
}