AT_ndpc2026_h コイン拾い

给定一个 $N \times N$ 的网格。令 $(i, j)$ 表示第 $i$ 行（自上而下）第 $j$ 列（自左而右）的方格。 每个方格的状态由 $N$ 个长度为 $N$ 的字符串 $S_1, S_2, \dots, S_N$ 描述。 如果 $S_i$ 的第 $j$ 个字符为 `@`，则 $(i, j)$ 这个格子里有一个硬币；如果是 `.`，则该格为空格。 你从 $(1,1)$ 这个格子出发，保证 $(1,1)$ 为空。 你可以不限次数（包括可以不操作）地进行如下操作： - 设当前位置为 $(i, j)$，你可以移动到右边的格子 $(i, j+1)$ 或下方的格子 $(i+1, j)$，不能移出网格。若移动到的格子内有硬币，必须捡起它。 对于每个 $x = 0, 1, \dots, 2N-2$，请解答： - 在进行若干（可能为零）次操作后，你到达某个格子 $(i, j)$，并且恰好捡到了 $x$ 枚硬币。这样的格子 $(i, j)$ 一共有多少个？

输入由标准输入给出，格式如下： > $N$ > $S_1$ > $S_2$ > $\vdots$ > $S_N$

输出 $2N-1$ 行。第 $i$ 行输出 $x = i-1$ 时的答案。

### 部分分数 本题采用部分分数制。 - 若你能解决 $N \leq 1500$ 的数据，可以获得 $2$ 分。 ### 样例解释 1 例如当 $x=0$ 时，可以到达的格子 $(i, j)$ 有 $(1,1), (2,1), (2,2), (3,2), (3,3)$，共 $5$ 个。 ### 数据范围 - $2 \leq N \leq 4000$ - $S_1, S_2, \dots, S_N$ 均为长度为 $N$ 的字符串，仅包含 `@` 与 `.` - $S_1$ 的第一个字符为 `.` - $N$ 为整数。 由 ChatGPT 5 翻译