← 返回题目列表

Codeforces · 2223/F

F. 稚嫩多彩的琴弦

中文机器翻译题面 查看原题

自从吉利一岁生日以来,吉利每年都会送他一条彩色绳子作为礼物,而且每一年的礼物都与往年不同。今年,吉利惊讶地发现他收到了所有可能的独特礼物!

我们称满足以下条件的彩色字符串为 有效:

  1. 由$$$m$$$类型的字符组成,其中$$$n_i$$$个字符属于第$$$i$$$类型;
  2. 第 $$$i$$$ 类型的每个字符都使用 $$$c_i$$$ 颜色之一着色;
  3. 该字符串可以是 减少 通过重复删除共享相同颜色的第 $$$i$$$ 类型的 $$$d_i$$$ 连续字符,将 转换为空字符串。

计算所有的数量 有效 彩色字符串,模 $$$998\,244\,353$$$。

如果两个彩色字符串至少在一个位置(字符类型或颜色)不同,则它们被视为不同。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$m$$$ ($$$1\le m\le 2\cdot 10^5$$$) — 类型数量。

接下来的 $$$m$$$ 行的第 $$$i$$$ 包含 $$$n_i, c_i, d_i$$$ ($$$1\le c_i \lt 998\,244\,353, 1\le n_i, d_i \le 10^8$$$) — 该行的字符总数$$$i$$$-th 类型、该类型的颜色数量以及所需的缩减长度。

保证所有测试用例的 $$$\left\lceil\frac{n_i}{d_i}\right\rceil$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在一行中输出一个整数,表示有效彩色字符串的数量,以 $$$998\,244\,353$$$ 为模。

示例

输入
复制

3
2
2 1 1
1 2 1
2
2 2 2
2 1 2
2
6 2 3
5 3 2

输出
复制

6
8
0

注意

对于示例,我们用 $$$1, 2, \ldots, \sum_{j=1}^m c_j$$$ 对所有颜色进行编号。其中颜色 $$$1+\sum_{j=1}^{i-1} c_j,\ldots,\sum_{j=1}^i c_j$$$ 属于第 $$$i$$$ 类型。下面,颜色 $$$1、2、3$$$ 分别为红色、蓝色和绿色。

对于第一个测试用例,有效字符串是:

  1. $$$[{\color{红色}1}, {\color{红色}1}, {\color{蓝色}2}]$$$
  2. $$$[{\color{红色}1}, {\color{红色}1}, {\color{绿色}3}]$$$
  3. $$$[{\color{红色}1}, {\color{蓝色}2}, {\color{红色}1}]$$$
  4. $$$[{\color{红色}1}, {\color{绿色}3}, {\color{红色}1}]$$$
  5. $$$[{\color{蓝色}2}, {\color{红色}1}, {\color{红色}1}]$$$
  6. $$$[{\color{绿色}3}, {\color{红色}1}, {\color{红色}1}]$$$

对于这些字符串中的任何一个,我们可以先删除唯一的$$$2$$$或$$$3$$$,然后删除$$$2$$$连续的$$$1$$$。

对于第二个测试用例,有效字符串是:

  1. $$$[{\color{红色}1}, {\color{红色}1}, {\color{绿色}3}, {\color{绿色}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{绿色}3}, {\color{红色}1}, {\color{红色}1}, {\color{绿色}3}]$$$
  6. $$$[{\color{绿色}3}, {\color{蓝色}2}, {\color{蓝色}2}, {\color{绿色}3}]$$$
  7. $$$[{\color{绿色}3}, {\color{绿色}3}, {\color{红色}1}, {\color{红色}1}]$$$
  8. $$$[{\color{绿色}3}, {\color{绿色}3}, {\color{蓝色}2}, {\color{蓝色}2}]$$$

对于第三个测试用例,可以很容易地看出没有有效的字符串。