526互联

Atcoder ABC259H Yet Another Path Counting

发布时间 2023-07-27 20:02:35作者: lhzawa

首先可以想到有组合数的方法：
令起点为 \((x1, y1)\)，终点为 \((x2, y2)\)，则路径方案数就为 \(\binom{x2 + y2 - x1 - y1}{x2 - x1}\)，这样设有 \(k\) 个相同颜色的点，时间复杂度就为 \(O(k^2)\)。

再考虑到还有 \(\text{DP}\) 方法：
令 \(f_{x, y}\) 为走到 \((x, y)\) 的方案数，不限制起点。
对于颜色都为 \(c\) 的点 \((x, y)\) 每个都可能成为起点，令 \(f_{x, y} = 1\)，转移式就为 \(f_{x, y}\leftarrow f_{x, y} + f_{x - 1, y} + f_{x, y - 1}\)，最后再统计每个点为终点的方案数 \(\sum\limits_{col_{x, y} = c} f_{x, y}\)。
时间复杂度就为 \(O(n^2)\)。

发现第一种方法在点数少时更优秀，第二种方法在点数多时更优秀，考虑设定一个阙值 \(B\)，在点数 \(\le B\) 时用第一种，\(> B\) 时用第二种。
对于第一种方法，上界肯定要尽量都是 \(B\)，时间复杂度 \(O(\frac{n^2}{B}\times B^2)\)，即 \(O(n^2B)\)；对于第二种方法，最多会出现 \(\frac{n^2}{B}\) 次这种情况，所以时间复杂度为 \(O(\frac{n^4}{B})\)。
于是总时间复杂度为 \(O(n^2B + \frac{n^4}{B})\)，当 \(B = n\) 时最优，时间复杂度为 \(O(n^3)\)。

// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: Ex - Yet Another Path Counting
// Contest: AtCoder - AtCoder Beginner Contest 259
// URL: https://atcoder.jp/contests/abc259/tasks/abc259_h
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using ll = long long;
const int N = 4e2 + 10;
ll C[2 * N][2 * N], f[N][N];
std::vector<std::pair<int, int> > u[N * N];
const ll mod = 998244353;
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1, x; j <= n; j++) {
			scanf("%d", &x);
			u[x].emplace_back(i, j);		
		}
	}
	C[0][0] = 1;
	for (int i = 1; i <= 2 * n; i++) {
		C[i][0] = C[i][i] = 1;
		for (int j = 1; j < i; j++) {
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
		}
	}
	ll ans = 0;
	for (int c = 1; c <= n * n; c++) {
		if ((int)u[c].size() <= n) {
			for (auto [x1, y1] : u[c]) {
				for (auto [x2, y2] : u[c]) {
					if (x1 <= x2 && y1 <= y2) {
						ans = (ans + C[x2 + y2 - x1 - y1][x2 - x1]) % mod;
					}
				}
			}
		} else {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					f[i][j] = 0;
				}
			}
			for (auto [x, y] : u[c]) {
				f[x][y] = 1;
			}
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					f[i][j] = (f[i][j] + f[i - 1][j] + f[i][j - 1]) % mod;
				}
			}
			for (auto [x, y] : u[c]) {
				ans = (ans + f[x][y]) % mod;
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}