有n*m的格子，并且是个跳格子的地方。每个格子有一个颜色c。现在你要从网格的左上角调到右下角，并且遵守以下规则：
设当前格子为(x,y)。
1)对于每次跳到的格子(tx,ty), tx>x, ty>y
2)对于每次跳到的格子(tx,ty), c[(tx,ty)]≠c[(x,y)]
问有多少种跳法。
输入描述:
第一行三个整数n,m,k,表示行和列以及颜色的范围[1,k]。
接下来n行，每行m个整数表示当前格子颜色。
对于100%的数据，n,m<=750, k<=n*m。
输出描述:
一个正整数s表示跳法数量。答案对10^9+7取模。
示例1
输入
4 4 4
1 1 1 1
1 3 2 1
1 2 4 1
1 1 1 1
输出
5
tiaogezi.cppview raw1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 755
#define P 1000000007
using namespace std;
int n,m,k;
int del[M*M];
int c[M][M],dp[M][M];
void CDQ(int L,int R){
if(L==R)return;
int mid=(L+R)>>1;
CDQ(L,mid);
int sum=0;
for(int j=2;j<=m;j++){
for(int k=L;k<=mid;k++){
sum=(sum+dp[k][j-1])%P;
del[c[k][j-1]]=(del[c[k][j-1]]+dp[k][j-1])%P;
}
for(int k=mid+1;k<=R;k++){
dp[k][j]=(dp[k][j]+sum)%P;
dp[k][j]=(dp[k][j]-del[c[k][j]]+P)%P;
}
}
for(int j=1;j<=m;j++)
for(int k=L;k<=mid;k++)
del[c[k][j]]=0;
CDQ(mid+1,R);
}
int main(){
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&c[i][j]);
dp[1][1]=1;
CDQ(1,n);
printf("%d\n",dp[n][m]);
return 0;
}
|