AT_abc241_h [ABC241Ex] Card Deck Score

题目描述

有若干张卡片，每张卡片上写有 $N$ 个整数中的某一个。具体来说，写有 $A_i$ 的卡片有 $B_i$ 张。
接下来，从这 $B_1+B_2+\cdots+B_N$ 张卡片中选出 $M$ 张。对于选出的 $M$ 张卡片，将它们上面写的 $M$ 个整数的乘积定义为这种选法的分数。
当写有相同整数的卡片无法区分时，请计算所有可能的 $M$ 张卡片的选法的分数之和，并输出其对 $998244353$ 取模的结果。

输入格式

输入以如下格式从标准输入读入。

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3 3
3 1
5 2
6 3

输出 #1

819

输入输出样例 #2

输入 #2

3 2
1 1
5 2
25 1

输出 #2

180

输入输出样例 #3

输入 #3

10 232657150901347497
139547946 28316250877914575
682142538 78223540024979445
110643588 74859962623690081
173455495 60713016476190629
271056265 85335723211047202
801329567 48049062628894325
864844366 54979173822804784
338794337 69587449430302156
737638908 15812229161735902
462149872 49993004923078537

输出 #3

39761306

说明/提示

限制条件

• $1 \leq N \leq 16$
• $1 \leq M \leq 10^{18}$
• $1 \leq A_i < 998244353$
• $1 \leq B_i \leq 10^{17}$
• 若 $i \neq j$，则 $A_i \neq A_j$
• $M \leq B_1+B_2+\cdots+B_N$
• 输入均为整数。

样例解释 1

选择 $3$ 张卡片的方法有如下 $6$ 种：

• 选 $1$ 张写有 $3$ 的卡片，$2$ 张写有 $5$ 的卡片。
• 选 $1$ 张写有 $3$ 的卡片，$1$ 张写有 $5$ 的卡片，$1$ 张写有 $6$ 的卡片。
• 选 $1$ 张写有 $3$ 的卡片，$2$ 张写有 $6$ 的卡片。
• 选 $2$ 张写有 $5$ 的卡片，$1$ 张写有 $6$ 的卡片。
• 选 $1$ 张写有 $5$ 的卡片，$2$ 张写有 $6$ 的卡片。
• 选 $3$ 张写有 $6$ 的卡片。

分数依次为 $75$、$90$、$108$、$150$、$180$、$216$，它们的总和为 $819$。

样例解释 2

“选 $1$ 张写有 $1$ 的卡片和 $1$ 张写有 $25$ 的卡片”与“选 $2$ 张写有 $5$ 的卡片”这两种选法的分数都是 $25$，但作为不同的选法应分别计数。

样例解释 3

请注意输出时要对 $998244353$ 取模。

由 ChatGPT 4.1 翻译