[THUPC 2022 初赛] 骰子旅行

Luogu
IDLGP8208
Time1000ms
Memory512MB
DifficultyP5
动态规划 DP2022O2优化期望THUPC
在乐队 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 找到了你,希望你能帮他算一下他这次骰子旅行的废话指数的期望值。 ## Input 输入的第一行包括三个正整数 $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$ 个输入的地点互不相同。 ## Output 输出一个数表示废话指数的期望。假设废话指数的期望化为最简分式后的形式为 $p/q$(即其中 $p, q$ 互质),请输出 $x$ 使得 $qx\equiv p \pmod{998,244,353}$ 且 $0\le x<998,244,353$。可以证明,在本题数据范围下,$x$ 存在且唯一。 [samples] ## Note 【样例解释 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】 转换前的答案为 $1625/432\approx 3.761574$,而 $432\times 274979351 = 118791079632 \equiv 1625 \pmod{998244353}$,所以模意义下的答案为 $274979351$。 【样例 3】 见附件。 【数据范围】 对于 $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}$。
Samples
Input #1
5 1 2
3 2 3 4
2 1 5
2 1 5
2 1 5
3 2 3 4
Output #1
499122178
Input #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
Output #2
274979351
API Response (JSON)
{
  "problem": {
    "name": "[THUPC 2022 初赛] 骰子旅行",
    "description": {
      "content": "在乐队 f 开巡演之前,按照惯例是要先组织乐队成员进行骰子旅行放松身心的。一次骰子旅行包括 $N$ 个地点,这些地点分别标号为 $1, 2, \\cdots, N$。乐队成员们事先约好在 $s_0$ 处集合;而到了骰子旅行当天,大家都来到了集合地点 $s_0$,骰子旅行就算正式开始了。 骰子旅行的一大乐趣就是由骰子决定旅行的下一个目的地。当然,这个骰子不一定非得是六面的。我们可以认为,如果当前乐队",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8208"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "在乐队 f 开巡演之前,按照惯例是要先组织乐队成员进行骰子旅行放松身心的。一次骰子旅行包括 $N$ 个地点,这些地点分别标号为 $1, 2, \\cdots, N$。乐队成员们事先约好在 $s_0$ 处集合;而到了骰子旅行当天,大家都来到了集合地点 $s_0$,骰子旅行就算正式开始了。\n\n骰子旅行的一大乐趣就是由骰子决定旅行的下一个目的地。当然,这个骰子不一定非得是六面的。我们可以认为,如果当前乐队...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments