P5014 水の三角(修改版)

题目背景

这个三角图真好看。。

这个是 $4$ 阶三角图。。

现在我们定义一个三角图是像上面一样的图。。

请求出一个无限大的三角图从 $1$ 号点走到 $u$ 号点的方案数。

有 $T$ 组询问。

第一行一个正整数 $T$ 。

第二行 $T$ 个正整数 $u_{i}$ 。

$T$ 行，共 $T$ 个正整数，表示答案模 $998244353$ 的结果。

1
2

3
1 3 6

1
2
3

1
2
6

$S u b t a s k 1 (10 p t s)$ : $1 \leq T \leq 100, 1 \leq u_{i} \leq 55$

$S u b t a s k 2 (20 p t s)$ : $1 \leq T \leq 100, 1 \leq u_{i} \leq 12502500$

$S u b t a s k 3 (30 p t s)$ : $1 \leq T \leq 100, 1 \leq u_{i} \leq 500000500000 u_{i} = \frac{x \times (x + 1)}{2}$

$S u b t a s k 4 (40 p t s)$ : $1 \leq T \leq 100, 1 \leq u_{i} \leq 500000500000$

给定三角网格图，求从点 $(1, 1)$ 走到点 $(n, m)$ 的路径方案数。

首先将三角推平，变成这个样子：

1
| \
2---3
|   | \
4---5---6

如果不走斜线，显然答案就是卡特兰数。总共向下走 $m - 1$ 步，向右走 $n - 1$ 步，方案数为：

C_{n + m - 2}^{m - 1} - C_{n + m - 2}^{m - 2}

接下来考虑走斜线的情况。假设走了 $i$ 次斜线，那么向下走的次数变为了 $n^{'} = n - 1 - i$ ，向右走的次数变为了 $m^{'} = m - 1 - i$ 。

走直线的所有排列方案数为：

C_{n^{'} + m^{'}}^{m^{'}} - C_{n^{'} + m^{'}}^{m^{'} - 1}

根据插板法，插入走斜线的方案数为：

C_{n^{'} + m^{'} + i}^{i}

根据乘法原理，总方案数为：

\sum_{i = 0}^{m - 1} C_{n^{'} + m^{'} + i}^{i} [C_{n^{'} + m^{'}}^{m^{'}} - C_{n^{'} + m^{'}}^{m^{'} - 1}]