自动搬运

查看原文

来自洛谷，原作者为

	lgvc 快乐学习，认真刷题，努力进步！

搬运于2025-08-24 21:45:30，当前版本为作者最后更新于2022-08-25 18:29:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是一篇不需要高级算法，数据结构的 $O(R^2C)$ 做法。

首先考虑暴力的 dp，$f_{i,j}$ 表示从 $(1,1)$ 走到 $(i,j)$ 的方案数，可以进行 $O(RC)$ 的转移，无法通过。

考虑在 dp 的时候，先枚举 $i$，再枚举 $j$，然后枚举到 $j$ 的时候把所有的第 $j-1$ 列，行数小于 $i$ 的点暴力插入（具体的，使用一个桶记录所有的用颜色 $i$ 结尾的方案数），同时维护桶内的数的和。转移就可以用和减去以自己的颜色结尾的方案数量。时间复杂度 $O(R^2C)$，需稍加常数优化并开起 O2 才可以通过。

代码：

#include <bits/stdc++.h>
#define MOD 1000000007
static char buf[1000000],*paa=buf,*pd=buf;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline int read(void) {
	register int x(0);register char c(getchar());
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x;
}
int R,C,K,dp[759][759],a[759][759];
long long v[759*759];
signed main(void) {
	R=read();C=read();K=read();
	for(int i=1;i<=R;i++) {
		for(int j=1;j<=C;j++) {
			a[i][j]=read();
		}
	}
	dp[1][1]=1;
	for(int i=2;i<=R;i++) {
		memset(v,0,sizeof(v));
		long long as=0;
		for(int j=2;j<=C;j++) {
			for(int k=1;k<i;k++) {
				v[a[k][j-1]]+=dp[k][j-1];
				as+=dp[k][j-1];
			}
			dp[i][j]=((as-v[a[i][j]])%MOD+MOD)%MOD;
		}
	}
	printf("%d",dp[R][C]);
	return 0;
}