【题解】S2OJ - #217 QQ空间的说说


题面

题目链接:S2OJ - #217 QQ空间的说说

难度:暂无评定

题目背景

You-Know-Who\text{You-Know-Who} 是一名有时候很菜的 OIer\text{OIer},有时候会颓废去刷 QQ\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(强男性)

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

题目描述

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

  • 测试总共有 nn 道题;
  • ii 题有 mim_i 个选项;
  • ii 题的第 jj 个选项,要么是一个数字 xx
  • 要么是一个大写英文字母 α\alpha,表示你如果选择了这个选项,你将得到测试结果 α\alpha,结束测试。

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

输入格式

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

输出格式

一行共 2626 个非负整数,分别表示 AZA \sim Z 型被选中的概率,模 998244353998244353 后的值。 提示:(x,p)=1,xp11(modp)(x,p) = 1,x^{p-1} \equiv 1 \pmod p

输入输出样例

输入样例#1

3
2 2 3
1 A
1 B

输出样例#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 显然 You-Know-Who\text{You-Know-Who}12\frac{1}{2} 的概率得到测试结果 AA12\frac{1}{2} 的概率得到测试结果 BB,测试结果 CZC\sim Z 都不可能得到。

数据规模与约定

对于 100%100\% 的数据:n5×106,i=1nmi107n \le 5 \times 10^6, \sum_{i=1}^{n} m_i \le 10^7 时间限制:2s2 \text{s} 空间限制:256MB256 \text{MB}

思路

记从第 11 题开始作答,跳转到某一题目 xx 的概率为 P(x)P(x),跳转到某一答案 α\alpha 的概率为 P(α)P(\alpha)

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

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

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

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

代码

#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;
}
【题解】S2OJ - #217 QQ空间的说说
本文作者
宝硕
发布于
2021-01-02
更新于
2021-01-31
许可协议
喜欢这篇文章?为什么不考虑打赏一下作者呢?
爱发电