CF1279D.Santa's Bot

普及+/提高

通过率:0%

时间限制:5.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Santa Claus has received letters from nn different kids throughout this year. Of course, each kid wants to get some presents from Santa: in particular, the ii-th kid asked Santa to give them one of kik_i different items as a present. Some items could have been asked by multiple kids.

Santa is really busy, so he wants the New Year Bot to choose the presents for all children. Unfortunately, the Bot's algorithm of choosing presents is bugged. To choose a present for some kid, the Bot does the following:

  • choose one kid xx equiprobably among all nn kids;
  • choose some item yy equiprobably among all kxk_x items kid xx wants;
  • choose a kid zz who will receive the present equipropably among all nn kids (this choice is independent of choosing xx and yy); the resulting triple (x,y,z)(x, y, z) is called the decision of the Bot.

If kid zz listed item yy as an item they want to receive, then the decision valid. Otherwise, the Bot's choice is invalid.

Santa is aware of the bug, but he can't estimate if this bug is really severe. To do so, he wants to know the probability that one decision generated according to the aforementioned algorithm is valid. Can you help him?

圣诞老人今年收到了来自 nn 个不同孩子的信件。当然,每个孩子都希望从圣诞老人那里得到一些礼物:具体而言,第 ii 个孩子请求圣诞老人送给他/她 kik_i 种不同物品中的一种作为礼物。某些物品可能被多个孩子同时请求。

圣诞老人非常忙碌,因此他希望“新年机器人”(New Year Bot)为所有孩子选择礼物。不幸的是,该机器人的选礼算法存在一个缺陷。当为某个孩子选择礼物时,机器人执行以下操作:

  • 在全部 nn 个孩子中等概率地随机选择一个孩子 xx;
  • 在孩子 xx 所希望获得的全部 kxk_x 种物品中等概率地随机选择一种物品 yy;
  • 在全部 nn 个孩子中等概率地随机选择一个将收到该礼物的孩子 zz(此选择与 xx 和 yy 的选择相互独立);由此得到的三元组 (x,y,z)(x, y, z) 被称为机器人的一个“决策”。

如果孩子 zz 所列的愿望清单中包含物品 yy,则该决策是有效的;否则,机器人的选择是无效的。

圣诞老人知晓这一缺陷,但他无法判断该缺陷是否真的严重。为此,他希望知道:按照上述算法生成的一个决策是有效的概率是多少?你能帮他计算吗?

输入格式

The first line contains one integer nn (1≤n≤1061 \le n \le 10^6) — the number of kids who wrote their letters to Santa.

Then nn lines follow, the ii-th of them contains a list of items wanted by the ii-th kid in the following format: kik_i ai,1a_{i, 1} ai,2a_{i, 2} ... ai,kia_{i, k_i} (1≤ki,ai,j≤1061 \le k_i, a_{i, j} \le 10^6), where kik_i is the number of items wanted by the ii-th kid, and ai,ja_{i, j} are the items themselves. No item is contained in the same list more than once.

It is guaranteed that ∑i=1nki≤106\sum \limits_{i = 1}^{n} k_i \le 10^6.

第一行包含一个整数 nn(1≤n≤1061 \le n \le 10^6)—— 表示给圣诞老人写信的孩子人数。

接下来是 nn 行,其中第 ii 行以如下格式给出第 ii 个孩子想要的物品列表:kik_i ai,1a_{i, 1} ai,2a_{i, 2} ... ai,kia_{i, k_i}(1≤ki,ai,j≤1061 \le k_i, a_{i, j} \le 10^6),其中 kik_i 表示第 ii 个孩子想要的物品数量,ai,ja_{i, j} 表示具体的物品。同一列表中不会出现重复的物品。

保证 ∑i=1nki≤106\sum \limits_{i = 1}^{n} k_i \le 10^6。

输出格式

Print the probatility that the Bot produces a valid decision as follows:

Let this probability be represented as an irreducible fraction xy\frac{x}{y}. You have to print x⋅y−1mod  998244353x \cdot y^{-1} \mod 998244353, where y−1y^{-1} is the inverse element of yy modulo 998244353998244353 (such integer that y⋅y−1y \cdot y^{-1} has remainder 11 modulo 998244353998244353).

输出机器人生成有效决策的概率,具体如下:

设该概率表示为既约分数 xy\frac{x}{y}。你需要输出 x⋅y−1mod  998244353x \cdot y^{-1} \mod 998244353,其中 y−1y^{-1} 是 yy 在模 998244353998244353 意义下的逆元(即满足 y⋅y−1≡1(mod998244353)y \cdot y^{-1} \equiv 1 \pmod{998244353} 的整数)。

输入输出样例

  • 输入#1

    2
    2 2 1
    1 1

    输出#1

    124780545
  • 输入#2

    5
    2 1 2
    2 3 1
    3 2 4 3
    2 1 4
    3 4 3 2

    输出#2

    798595483

输入解题思路,AI测评打分。不知道怎么写?

首页