#1175. QOJ 467_2576

    ID: 1175 传统题 2000ms 512MiB 尝试: 1 已通过: 0 难度: 省选/NOI- 上传者: 标签>QOJ来源:qoj.ac 467_2576答案:本地AC标程生成动态规划数学

QOJ 467_2576

QOJ 467_2576

题目描述

1 麻将 1.1 题目描述 九条可怜是一个热爱打麻将的女孩子。因此她出了一道和麻将相关的题目,希望这题不会 让你对麻将的热爱消失殆尽。 今天,可怜想要打麻将,但是她的朋友们都去下自走棋了,因此可怜只能自己一个人打。可 怜找了一套特殊的麻将,它有n(n ≥5) 种不同的牌,大小分别为1 到n,每种牌都有4 张。 定义面子为三张大小相同或者大小相邻的麻将牌,即大小形如i, i, i(1 ≤i ≤n) 或者 i, i + 1, i + 2(1 ≤i ≤n −2)。定义对子为两张大小相同的麻将牌,即大小形如i, i(1 ≤i ≤n)。 定义一个麻将牌集合S 是胡的当且仅当它的大小为14 且满足下面两个条件中的至少一个: • S 可以被划分成五个集合S1 至S5。其中S1 为对子,S2 至S5 为面子。 • S 可以被划分成七个集合S1 至S7,它们都是对子,且对应的大小两两不同。 举例来说,下列集合都是胡的(这儿只标记了大小): • {1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 9} • {1, 1, 2, 2, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8} • {1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7} 而下列集合都不是胡的: • {1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 9} • {1, 1, 1, 1, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8} • {1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 9, 11} 可怜先摸出了13 张牌,并把剩下的4n −13 张牌随机打乱。打乱是等概率随机的,即所有 (4n −13)! 种排列都等概率出现。 对于一个排列P,可怜定义Si 为可怜事先摸出的13 张牌加上P 中的前i 张牌构成的集 合,定义P 的权值为最小的i 满足Si 存在一个子集是胡的。如果你对麻将比较熟悉,不难发 2

现P 的权值就是理论上的最早胡牌巡目数。注意到n ≥5 的时候,S4n−13 总是存在胡的子集 的,因此P 的权值是良定义的。 现在可怜想要训练自己的牌效,因此她希望你能先计算出P 的权值的期望是多少。 1.2 输入Ḑ式 第一行输入一个整数n,表示这副特殊的麻将牌中的大小种类数。 接下来输入13 行每行两个整数w, t(1 ≤w ≤n, 1 ≤t ≤4),表示可怜最开始摸出的第i 张 牌是大小为w 的第t 张牌,保证(w, t) 二元组两两不同。 1.3 输出Ḑ式 输出一行一个整数,表示答案对998244353 取模后的值。即如果答案的最简分数表示为 x y(x ≥0, y ≥1, gcd(x, y) = 1),你需要输出x × y−1 mod 998244353。 1.4 ḋ例输入 9 1 1 1 2 1 3 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 9 2 9 3 1.5 ḋ例输出 1 1.6 ḋ例㾷䞞 上述牌型叫做纯正九莲宝灯,不难发现不管再加一张什么牌它都是胡的。所以对于所有排 列P,权值都是1,因此权值的期望就是1。 3

1.7 数据㣗ೈ与约定 对于20% 的数据,n = 5。 对于50% 的数据,n ≤13。 对于另外20% 的数据,n ≤100, wi = i, ti = 1。 对于另外20% 的数据,n ≤100, wi = ⌈i 4⌉, ti = i mod 4 + 1。 对于100% 的数据,5 ≤n ≤100。 4

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

100
2 3
0