思路
朴素的想法就是一个 \(O(n^2m^2)\) 的转移：
\[f_{i,j}=\sum_{x=1}^{i-1}\sum_{y=1}^{j-1}f_{x,y}*[a_{i,j}!=a_{x,y}] \]约束条件如此多，思考用 cdq分治 来优化
我们考虑对行进行分治，先分治 \([l,mid]\)
然后暴力枚举列，用 \([l,mid]\) 来更新 \((mid,r]\)
每次枚举列 \(j\) 转移完，都将 \(\sum_{i=l}^{mid}f_{i,j}\) 加到 \(sum\) 中，并更新 \(s[a_{i,j}]\) （用来减去相同数字的贡献）
转移的方程就为：
\[f_{i,j}+=sum-s[a_{i,j}] \]最后分治 \([mid + 1, r]\)
代码
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#define LL long long
#define FOR(i, x, y) for(int i = (x); i <= (y); i++)
#define ROF(i, x, y) for(int i = (x); i >= (y); i--)
#define PFOR(i, x) for(int i = he[x]; i; i = r[i].nxt)
inline int reads()
{
int sign = 1, re = 0; char c = getchar();
while(c < '0' || c > '9'){if(c == '-') sign = -1; c = getchar();}
while('0' <= c && c <= '9'){re = re * 10 + (c - '0'); c = getchar();}
return sign * re;
}
const int mod = 1e9 + 7;
inline int add(int a, int b) {return a + b >= mod ? a + b - mod : a + b;}
inline int sub(int a, int b) {return a - b < 0 ? a - b + mod : a - b;}
int n, m, k, a[755][755], f[755][755], s[562505];
void solve(int l, int r)
{
if(l == r) return;
int mid = (l + r) >> 1;
solve(l, mid);
int sum = 0;
FOR(j, 1, m)
{
FOR(i, mid + 1, r) f[i][j] = add(f[i][j], sub(sum, s[a[i][j]]));
FOR(i, l, mid) sum = add(sum, f[i][j]), s[a[i][j]] = add(s[a[i][j]], f[i][j]);
}
FOR(i, 1, k) s[i] = 0;
solve(mid + 1, r);
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
n = reads(), m = reads(), k = reads();
FOR(i, 1, n) FOR(j, 1, m) a[i][j] = reads();
f[1][1] = 1;
solve(1, n);
printf("%d", f[n][m]);
return 0;
}