S2OJ - 217. QQ 空间的说说

#题面

难度：暂无评定

#题目背景

$\text{You-Know-Who}$ 是一名有时候很菜的 $\text{OIer}$ ，有时候会颓废去刷 $\text{QQ}$ 空间。一天，他看到了这样的一条说说《最近很火的 ABO 性别测试。我是男 O，你们呢？》。内容是这样的：

请根据你的回答选择下一道题：

1.拥有属于自己的电脑的时候，你会精心挑选？
a.显示屏 - 2   b.键盘 - 3   c.鼠标 - 4

2.通常你会什么时候开始换夏装？
a.按日历节气来换 - 3   b.春天快结束的时候 - 5   c.热的不得不换衣服的时候 - 4

3.自己一个人的时候，你的坐姿是？
a.双腿并拢在一起 - 6   b.双腿叉开 - 4   c.翘二郎腿 - 5

4.遇到自己喜欢的人你会？
a.等待对方向自己告白 - 5   b.单恋对方 - 6   c.第一时间主动告白 - 7

5.你最喜欢什么材料的衣服？
a.丝绸 - 6   b.纱料 - 7   c.布料 - 8

6.自己做饭后，通常厨房什么样子？
a.乱得惨不忍睹 - 7   b.非常整洁干净 - 8   c.有一点点凌乱 - 9

7.你觉得历史战争电视剧对于你来说？
a.特别帅 - 8   b.很无语 - 9   c.特别有吸引力 - 10

8.每次出门的时候，你最注意的是？
a.自己是不是带了想带的东西 - 9   b.自己的味道 - 10   c.自己的发型和着装 - B

9.你认为工作套装和西服给你的感觉是？
a.庄重的服饰 - D   b.过于拘谨的服饰 - E    c.美丽的服饰 - A

10.如果为自己的房子选颜色的话你会选？
a.红色 - B   b.白色 - C   c.紫色 - D

A型 -> 女性omega（强女性）   B型 -> 男性omega（弱女性）   C型 -> 中性beta   D型 -> 女性alpha（弱男性）   E型 -> 男性alpha（强男性）

反正 $\text{You-Know-Who}$ 才不会相信这些假假的东西，于是他每次都是随机地选择一个选项，然后跳到对应的题目，继续随机地选择，直到选择出一个测试结果为止。

#题目描述

我们形式化地定义一下这样类型的测试：

测试总共有 $n$ 道题；
第 $i$ 题有 $m_i$ 个选项；
第 $i$ 题的第 $j$ 个选项，要么是一个数字 $x$
要么是一个大写英文字母 $\alpha$ ，表示你如果选择了这个选项，你将得到测试结果 $\alpha$ ，结束测试。

$\text{Steaunk}$ 想知道对于一个给定的形如上面描述的测试，如果 $\text{You-Know-Who}$ 一开始从第一道题开始作答，每次都是等概率随机地选择其中一个选项，然后执行对应的操作，直到得到一个大写英文字母 $\alpha$ 表示的测试结果，结束测试，那么对于 $A \sim Z$ 中的每一个测试结果被选中的概率是多少？

#输入格式

第一行共一个正整数 $n$ ，表示题目的数量。接下来有 $n$ 行，每行第一个正整数 $m_i$ 表示第 $i$ 道题有 $m_i$ 个选项；接着有 $m_i$ 个由空格分开的字符串，表示选项；这个字符串要么可以表示为一个正整数 $x$ ，满足 i < x \le n，表示选择这个选项你会跳转到第 $x$ 题继续作答；要么是一个大写英文字母 $\alpha$ ，表示选择这个选项，你得到测试结果 $\alpha$ ，结束测试。

#输出格式

一行共 $26$ 个非负整数，分别表示 $A \sim Z$ 型被选中的概率，模 $998244353$ 后的值。提示： $(x,p) = 1,x^{p-1} \equiv 1 \pmod p$ 。

#输入输出样例

输入样例#1

输出样例#1

499122177 499122177 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

样例说明#1 显然 $\text{You-Know-Who}$ 有 $\frac{1}{2}$ 的概率得到测试结果 $A$ ， $\frac{1}{2}$ 的概率得到测试结果 $B$ ，测试结果 $C\sim Z$ 都不可能得到。

#数据规模与约定

对于 $100\%$ 的数据： $n \le 5 \times 10^6, \sum_{i=1}^{n} m_i \le 10^7$ 时间限制： $2 \text{s}$ 空间限制： $256 \text{MB}$

#思路

记从第 $1$ 题开始作答，跳转到某一题目 $x$ 的概率为 $P(x)$ ，跳转到某一答案 $\alpha$ 的概率为 $P(\alpha)$ 。

很容易可以得出一个初始条件 $P(1) = 1$ 。

所求的答案即为 $P(A), P(B), P(C), \ldots, P(Z)$ 。

如果对于题目 $i$ ，设它能跳转到题目或答案 $x_1, x_2, x_3, \ldots, x_{m_i}$ ，那么可以推出一个递推式： $P(x_j) \gets P(x_j) + \large{\frac{p(i)}{m_i}}$ ，之后按照该式递推即可。

坑点： $\text{概率}$ 和 $\large{\frac{\text{各点到达次数}}{\text{到达次数总和}}}$ 是不一样的，要把出发点概率乘上选项的数量，并分配到每一个终点（考场上我因为不知道这个写炸了）。

#代码

C++

#include <bits/stdc++.h>

using namespace std;

const int mod = 998244353;

int n, m, t, p[5000050], inv[10000005];

int read() {
    int res = 0;
    char ch = getchar();
    while (!isdigit(ch) && !isalpha(ch)) {
        ch = getchar();
    }
    if (ch >= 'A') {
        return ch - 64 + n;
    }
    while (isdigit(ch)) {
        res = res * 10 + ch - 48;
        ch = getchar();
    }
    return res;
}

long long binpow(long long a, long long b) {
    a %= mod;
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    cin >> n;
    p[1] = 1;
    for (int i = 1; i <= n; i++) {
        cin >> m;
        if (!inv[m]) {
            inv[m] = binpow(m, mod - 2);
        }
        p[i] = (long long)p[i] * inv[m] % mod;
        for (int j = 1; j <= m; j++) {
            t = read();
            p[t] = (p[t] + p[i]) % mod;
        }
    }
    for (int i = 1; i <= 26; i++) {
        cout << p[n + i] << ' ';
    }
    cout << endl;
    return 0;
}