[文章目录]
Description
游戏在一个R*C的网格上进行，每个格子有一个取值在1-k之间的整数标号，奶牛开始在左上角的格子，目的是通过若干次跳跃后到达右下角的格子，当且仅当格子A和格子B满足如下条件时能从格子A跳到格子B：
1.B格子在A格子的严格右方(B的列号严格大于A的列号)
2.B格子在A格子的严格下方(B的行号严格大于A的行号)
3.B格子的标号和A格子的标号不同
请你帮助奶牛计算出从左上角的格子到右下角的格子一共有多少种不同的方案 R,C<=750 K<=R*C
CDQ分治。
桶维护不同标号的格子的方案数，分治列，按照行入桶。复杂度O(R*C*logR)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod=1000000007;
int n,m,lim,mp[760][760],f[760][760],num[760*760];
inline int Add(int x){return x>=mod ? x-mod : x;}
inline int Cut(int x){return x<0 ? x+mod : x;}
void solve(int l,int r)
{
if(l==r) return ;
int mid=(l+r)>>1;
solve(l,mid); int sum=0;
for(int i=1;i<m;++i)
{
for(int j=l;j<=mid;++j)
{
sum=Add(sum+f[j][i]);
num[mp[j][i]]=Add(num[mp[j][i]]+f[j][i]);
}
for(int j=mid+1;j<=r;++j)
{
f[j][i+1]=Add(f[j][i+1]+sum);
f[j][i+1]=Cut(f[j][i+1]-num[mp[j][i+1]]);
}
}
for(int i=l;i<=mid;++i) for(int j=1;j<m;++j) num[mp[i][j]]=0;
solve(mid+1,r);
}
int main()
{
scanf("%d%d%d",&n,&m,&lim);
for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",&mp[i][j]);
f[1][1]=1;
solve(1,n);
printf("%d",f[n][m]);
return 0;
}