QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

#3242. 骰子旅行

統計

题目描述

在乐队 f 开巡演之前,按照惯例是要先组织乐队成员进行骰子旅行放松身心的。一次骰子旅行包括 $N$ 个地点,这些地点分别标号为 $1, 2, \cdots, N$。乐队成员们事先约好在 $s_0$ 处集合;而到了骰子旅行当天,大家都来到了集合地点 $s_0$,骰子旅行就算正式开始了。

骰子旅行的一大乐趣就是由骰子决定旅行的下一个目的地。当然,这个骰子不一定非得是六面的。我们可以认为,如果当前乐队成员们位于地点 $i$,那么下一个目的地会等概率地从 $m_i$ 个互不相同的候选地点中产生,这些候选地点分别是 $l_{i, 1}, l_{i, 2}, \cdots, l_{i, m_i}$。我们记第 $t$ 次投掷的结果是 $s_t$,那么第 $(t+1)$ 次将会前往 $s_t$ 处掷骰子。第 1 次投掷在起点 $s_0$ 处进行;而由于乐队之后还需要为了巡演排练,事先约定无论前往了哪些地点,投掷完第 $T$ 次骰子,前往 $s_T$ 后骰子旅行都得结束。

当然,享受 $s_0, s_1, \cdots, s_T$ 这些景点也是骰子旅行的一大乐趣。无论是否之前来过,每次到一个地点 $s_t$,乐队成员们都会尽情地浏览美景,品尝美食。只是如果之前来过 $s_t$,负责掷骰子的键盘手 S 在掷这第 $(t+1)$ 次骰子之前一定会说:“上次来到 $s_t$ 仿佛还是上一次 $t'$,上一次在这里掷出了 $s_{t'+1}$,不知道这一次会掷出什么结果。”鼓手 Y 特别喜欢废话梗,所以每次 S 说这句话时,他都会把 $s_{t'+1}$ 记下来。特别地,如果 $s_T$ 是之前经过的地点,那么 S 会说:“上次来到 $s_t$ 仿佛还是上一次 $t'$,上一次在这里掷出了 $s_{t'+1}$,不过这一次就不投掷了,因为骰子旅行到这里就要告一段落了。”当然,Y 也会把这个 $s_{t'+1}$ 记下来。

作为这次骰子旅行的总结,Y 会把所有记录下来的 $s_{t'+1}$ 加起来,作为 S 的废话指数。

f 的下一次巡演马上就要开始了,于是 S 又盘算着带大家去参加骰子旅行。听说你是 f 的粉丝,S 找到了你,希望你能帮他算一下他这次骰子旅行的废话指数的期望值。

输入格式

从标准输入读入数据。

输入的第一行包括三个正整数 $N, s_0, T$,分别表示可能涉及地点的个数,骰子旅行的起点和骰子旅行中投掷骰子的次数。

接下来 $N$ 行,第 $i\ (1\le i\le N)$ 行先输入一个正整数 $m_i$,表示地点 $i$ 的下一个目的地的候选地点数;接着输入 $m_i$ 个正整数,表示这 $m_i$ 个地点 $l_{i, 1}, l_{i, 2}, \cdots, l_{i, m_i}$。保证对于任意 $i$,$m_i$ 个输入的地点互不相同。

输出格式

输出到标准输出。

输出一个数表示废话指数的期望。假设废话指数的期望化为最简分式后的形式为 $p/q$(即其中 $p, q$ 互质),请输出 $x$ 使得 $qx\equiv p \pmod{998,244,353}$ 且 $0\le x< 998,244,353$。可以证明,在本题数据范围下,$x$ 存在且唯一。

样例1输入

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

样例1输出

499122178

样例1解释

对答案有贡献的方案为:从点 $1$ 出发走到 $2, 3, 4$ 中的任意一个点并返回点 $1$。对于某个点 $i (i=2, 3, 4)$,走到点 $i$ 并返回点 $1$ 的概率为 $1/6$,而贡献为 $i$,故期望为 $$\frac{1}{6}\times (2+3+4) = \frac{3}{2}.$$

由 $499122178 \times 2 = 998244356 \equiv 3 \pmod {998244353}$ 可知 $3/2$ 在模 $998,244,353$ 意义下为 $499,122,178$,所以正确输出为 $499,122,178$。

样例2输入

7 1 4
6 2 3 4 5 6 7
6 1 3 4 5 6 7
6 1 2 4 5 6 7
6 1 2 3 5 6 7
6 1 2 3 4 6 7
6 1 2 3 4 5 7
6 1 2 3 4 5 6

样例2输出

274979351

样例2解释

转换前的答案为 $1625/432\approx 3.761574$,而 $432\times 274979351 = 118791079632 \equiv 1625 \pmod{998244353}$,所以模意义下的答案为 $274979351$。

样例3

见题目目录下的 3.in3.ans

子任务

对于 $100\%$ 的数据,保证 $1\le N\le 100$,$1\le T\le 100$,$1\le s_0\le N$,$1\le m_i\le N$,$\sum_{i=1}^N m_i\le 5000$,$1\le l_{i, j}\le N$,且 $\forall 1\le i\le N, \forall 1\le j_1< j_2\le m_i, l_{i, j_1}\ne l_{i, j_2}$。

About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

  1. This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
  2. Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
  3. Issues must be filed in English or Chinese only.
  4. Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0

No issues in this category.