AT_abc241_h.[ABC241Ex] Card Deck Score

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有若干张卡片，每张卡片上写有 $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
```
3 3
3 1
5 2
6 3
```
输出#1
```
819
```
输入#2
```
3 2
1 1
5 2
25 1
```
输出#2
```
180
```

输入#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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页