题解 [ABC259Ex] Yet Another Path Counting

首先，每种颜色互不干扰，因此考虑对每种颜色统计答案。

有两种解法：

• 枚举起始格子 \((x,y)\) 和结尾格子 \((z,w)\)，由组合数易知共有 \(\binom{z-x+w-y}{z-x}\) 种路径。时间复杂度为 \(\mathcal O(k^2)\)，其中 \(k\) 为这种颜色格子数量。
• 动态规划统计这种颜色的格子到每个格子的路径数。时间复杂度为 \(\mathcal O(n^2)\)。

进行根号分治。当 \(k\le n\) 时，第一种解法总复杂度不超过 \(\mathcal O(n^3)\)；当 \(k > n\) 时，此类情况不超过 \(n\) 次，第二种解法总复杂度不超过 \(\mathcal O(n^3)\)。

// Problem: AT_abc259_h [ABC259Ex] Yet Another Path Counting
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_abc259_h
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll N = 405, mod = 998244353;

ll n, a[N][N], dp[N][N], fac[N*2], ifac[N*2], ans;
vector<tuple<ll, ll> > pos[N*N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
void initC(ll x) {
	fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
	rep(i, 2, x) {
		fac[i] = fac[i-1] * i % mod;
		ifac[i] = (mod - mod / i) * ifac[mod%i] % mod;
	}
	rep(i, 2, x) ifac[i] = ifac[i-1] * ifac[i] % mod;
}
ll C(ll x, ll y) {
	if(x < 0 || y < 0 || x < y) return 0;
	return fac[x] * ifac[y] % mod * ifac[x-y] % mod;
}

int main() {
	initC(N*2-1);
	scanf("%lld", &n);
	rep(i, 1, n) {
		rep(j, 1, n) {
			scanf("%lld", &a[i][j]);
			pos[a[i][j]].emplace_back(i, j);
		}
	}
	rep(c, 1, n*n) {
		if(!pos[c].empty()) {
			if((ll)pos[c].size() <= n) {
				ll sz = pos[c].size();
				rep(i, 0, sz-1) {
					rep(j, 0, sz-1) {
						ll x = get<0>(pos[c][j]) + get<1>(pos[c][j]) - get<0>(pos[c][i]) - get<1>(pos[c][i]);
						ll y = get<0>(pos[c][j]) - get<0>(pos[c][i]);
						ans += C(x, y);
						ans %= mod;
					}
				}
			}
			else {
				rep(i, 1, n) {
					rep(j, 1, n) {
						dp[i][j] = (a[i][j] == c);
						dp[i][j] += dp[i-1][j]; dp[i][j] %= mod;
						dp[i][j] += dp[i][j-1]; dp[i][j] %= mod;
						if(a[i][j] == c) {
							ans += dp[i][j];
							ans %= mod;
						}
					}
				}
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}

原文地址：http://www.cnblogs.com/ruierqwq/p/abc259h.html