思路与结论

• 等价条件：涂色有效当且仅当不存在蓝格子 $(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}$。

• 因而总答案为

题目内容

给定一个由 $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)$ ；