思路与结论

• 等价条件：涂色有效当且仅当不存在蓝格子 $(i_b,j_b)$ 与红格子 $(i_r,j_r)$ 使得 $i_b\le i_r$ 且 $j_b\le j_r$。即不存在“蓝在红的左下”。

• 设红色集合的向下闭包（在坐标偏序下）为理想 $I$。每个有效涂色唯一对应到某个理想 $I$，并且：

  • $I$ 内不可为蓝；所有 $I$ 的极大元必须为红；其余（在 $I$ 内）可红/白；$I$ 外不可为红，可蓝/白。
  • 对固定 $I$ 的方案数为 $2^{n^{2}-m(I)}$，其中 $m(I)$ 是 $I$ 的极大元个数。

• 理想与从 $(0,0)$ 到 $(n,n)$ 的单调路径一一对应；$m(I)$ 等于该路径中“右转下（R→D）”拐角数 $k$。

• 含 $k$ 个 R→D 拐角的路径条数为 $\binom{n}{k}^{2}$。

• 因而总答案为

• 实现：预处理 $\binom{n}{k}$，线性求和。用 $\text{inv2}=\frac{1}{2}\equiv 499122177$（模逆元），并计算 $2^{n^{2}}$ 模幂。

C++

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 998244353;

// 快速幂
long long modpow(long long a, long long e) {
	long long r = 1 % MOD;
	a %= MOD;
	while (e > 0) {
		if (e & 1) r = (r * a) % MOD;
		a = (a * a) % MOD;
		e >>= 1;
	}
	return r;
}

// 组合数预处理
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	if (!(cin >> n)) return 0;

	// 预处理 factorial 与 invfactorial
	vector<long long> fact(n + 1), invfact(n + 1);
	fact[0] = 1;
	for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i % MOD;
	invfact[n] = modpow(fact[n], MOD - 2);
	for (int i = n; i >= 1; --i) invfact[i - 1] = invfact[i] * i % MOD;

	auto C = [&](int N, int K) -> long long {
		if (K < 0 || K > N) return 0;
		return fact[N] * invfact[K] % MOD * invfact[N - K] % MOD;
	};

	// 计算 S = sum_{k=0..n} C(n,k)^2 * inv2^k
	const long long inv2 = (MOD + 1) / 2; // 499122177
	long long S = 0;
	long long cur = 1; // inv2^0
	for (int k = 0; k <= n; ++k) {
		long long comb = C(n, k);
		long long term = comb * comb % MOD * cur % MOD;
		S += term;
		if (S >= MOD) S -= MOD;
		cur = cur * inv2 % MOD;
	}

	// 2^(n^2)
	long long pow2 = modpow(2, 1LL * n * n);

	long long ans = pow2 * S % MOD;
	cout << ans << "\n";
	return 0;
}

Python

import sys

MOD = 998244353

def modpow(a, e, mod=MOD):
    r = 1
    a %= mod
    while e > 0:
        if e & 1:
            r = (r * a) % mod
        a = (a * a) % mod
        e >>= 1
    return r

def main():
    data = sys.stdin.read().strip().split()
    n = int(data[0])

    # 预处理阶乘与逆元
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % MOD
    invfact = [1] * (n + 1)
    invfact[n] = modpow(fact[n], MOD - 2)
    for i in range(n, 0, -1):
        invfact[i - 1] = invfact[i] * i % MOD

    def C(N, K):
        if K < 0 or K > N:
            return 0
        return fact[N] * invfact[K] % MOD * invfact[N - K] % MOD

    inv2 = (MOD + 1) // 2  # 499122177
    S = 0
    cur = 1  # inv2^0
    for k in range(n + 1):
        comb = C(n, k)
        term = comb * comb % MOD * cur % MOD
        S = (S + term) % MOD
        cur = (cur * inv2) % MOD

    pow2 = modpow(2, n * n)
    ans = (pow2 * S) % MOD
    print(ans)

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
	static final long MOD = 998244353L;

	static long modpow(long a, long e) {
		long r = 1 % MOD;
		a %= MOD;
		while (e > 0) {
			if ((e & 1) == 1) r = (r * a) % MOD;
			a = (a * a) % MOD;
			e >>= 1;
		}
		return r;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine().trim());

		// 预处理 factorial 与 invfactorial
		long[] fact = new long[n + 1];
		long[] invfact = new long[n + 1];
		fact[0] = 1;
		for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
		invfact[n] = modpow(fact[n], MOD - 2);
		for (int i = n; i >= 1; i--) invfact[i - 1] = invfact[i] * i % MOD;

		java.util.function.BiFunction<Integer, Integer, Long> C = (N, K) -> {
			if (K < 0 || K > N) return 0L;
			return fact[N] * invfact[K] % MOD * invfact[N - K] % MOD;
		};

		long inv2 = (MOD + 1) / 2; // 499122177
		long S = 0;
		long cur = 1; // inv2^0
		for (int k = 0; k <= n; k++) {
			long comb = C.apply(n, k);
			long term = comb * comb % MOD * cur % MOD;
			S += term;
			if (S >= MOD) S -= MOD;
			cur = cur * inv2 % MOD;
		}

		long pow2 = modpow(2, 1L * n * n);
		long ans = pow2 * S % MOD;
		System.out.println(ans);
	}
}

题目内容

给定一个由 $n+1$ 条横线、$n+1$ 条竖线构成的网格 (即划分成 $n×n$ 个单元格、$(n+1)×(n+1)$ 个格点)，我们使用 $(i,j)$ 表示网格中从上往下数第 $i$ 条直线和从左往右数第 $j$ 条直线交叉所在的格点，下标从 $0$ 开始。

每个单元格可以被染成蓝色、红色或白色中的一种颜色，故我们一共有 $3^{n×n}$ 种不同的涂色方案。

你从起点格点 $(0,0)$ 出发。假设当前格点为 $(x,y)$ ，你可以执行以下两种操作之一：

• 如果 $x<n$，沿竖线向下移动到格点 $(x +1,y)$ ；

• 如果 $y< n$ ，沿横线向右移动到格点 $(x,y+ 1)$ 。

当到达终点格点 $(n,n)$ 时，所经过的路径将网格中的单元格分为两部分：路径的左下方和右上方区域：

• 左下方区域：格点 $(0,0)、(n,0)、(n,n)$ 沿路径返回 $(0,0)$ 的区域；

• 右上方区域：格点 $(0,0)、(0,n)、(n,n)$ 沿路径返回 $(0,0)$ 的区域。

显然，一个单元格要么属于路径的左下方区域，要么属于路径的右上方区域。

定义：如果右上方区域不包含任何红色单元格且左下方区域不包含任何蓝色单元格，则称该路径为「良好路径」。如果对于某种涂色方案，存在至少一条「良好路径」，则认为该涂色方案是有效的。

在所有 $3^{n×n}$ 种涂色方案中，计算有效涂色方案的数量。由于答案可能很大，请将答案对 $998$ $244$ $353$ 取模后输出。

输入描述

输入共一行，包含一个整数 $n(1≤n≤5000)$ ，表示网格的大小。

输出描述

输出一个整数，表示有效涂色方案的数量对 $998$ $244$ $353$ 取模后的结果。

样例1

输入

1

输出

3

样例2

输入

2

输出

52

样例3

输入

3

输出

4032