CF2223F Zhily and Colorful Strings

自从 Jily 的第一个生日开始，Zhily 每年都会送他一根彩色字符串作为礼物，而且每一年的礼物都与前面所有的礼物不同。今年，Jily 惊讶地发现他已经收到了所有可能的不同礼物！ 我们称满足以下条件的彩色字符串为“合法”的： 1. 它由 $m$ 种字符类型组成，对于第 $i$ 种字符，恰好有 $n_i$ 个； 2. 第 $i$ 种字符的每个字符可以被涂成 $c_i$ 种颜色中的任意一种； 3. 可以通过多次删除 $d_i$ 个连续且颜色相同的第 $i$ 种字符，将该字符串化简为空字符串。 请你计算所有合法彩色字符串的数量，对 $998\,244\,353$ 取模。 如果两个彩色字符串中有至少一个位置字符类型或颜色不同，则认为这两个字符串是不同的。

每组测试数据包含多组测试用例。第一行是整数 $t$（$1 \le t \le 10^4$），表示测试用例数。 每个测试用例第一行包含一个整数 $m$（$1 \le m \le 2\cdot 10^5$），表示字符类型数。 接下来的 $m$ 行，每行包括 $n_i, c_i, d_i$（$1 \le c_i < 998\,244\,353, 1 \le n_i, d_i \le 10^8$），含义分别为第 $i$ 种字符的总数、该类型的颜色数和所需的归约长度。 保证所有测试用例中 $\sum \left\lceil \frac{n_i}{d_i} \right\rceil \le 2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示合法彩色字符串的数量，对 $998\,244\,353$ 取模。

以编号 $1,2,\ldots, \sum_{j=1}^m c_j$ 表示所有颜色，其中编号 $1+\sum_{j=1}^{i-1} c_j$ 到 $\sum_{j=1}^i c_j$ 的颜色属于第 $i$ 种字符。下文中，颜色 $1,2,3$ 分别用红、蓝、绿表示。 对于第一个测试用例，合法字符串为： 1. $[{\color{red}1}, {\color{red}1}, {\color{blue}2}]$ 2. $[{\color{red}1}, {\color{red}1}, {\color{green}3}]$ 3. $[{\color{red}1}, {\color{blue}2}, {\color{red}1}]$ 4. $[{\color{red}1}, {\color{green}3}, {\color{red}1}]$ 5. $[{\color{blue}2}, {\color{red}1}, {\color{red}1}]$ 6. $[{\color{green}3}, {\color{red}1}, {\color{red}1}]$ 在这些字符串中，总可以先删除唯一的 $2$ 或 $3$，然后再删除 $2$ 个连续的 $1$。 对于第二个测试用例，合法字符串为： 1. $[{\color{red}1}, {\color{red}1}, {\color{green}3}, {\color{green}3}]$ 2. $[{\color{red}1}, {\color{green}3}, {\color{green}3}, {\color{red}1}]$ 3. $[{\color{blue}2}, {\color{blue}2}, {\color{green}3}, {\color{green}3}]$ 4. $[{\color{blue}2}, {\color{green}3}, {\color{green}3}, {\color{blue}2}]$ 5. $[{\color{green}3}, {\color{red}1}, {\color{red}1}, {\color{green}3}]$ 6. $[{\color{green}3}, {\color{blue}2}, {\color{blue}2}, {\color{green}3}]$ 7. $[{\color{green}3}, {\color{green}3}, {\color{red}1}, {\color{red}1}]$ 8. $[{\color{green}3}, {\color{green}3}, {\color{blue}2}, {\color{blue}2}]$ 对于第三个测试用例，可以很容易地发现没有合法字符串。 由 ChatGPT 5 翻译