AT_arc210_e.[ARC210E] Subset Sum Gaps

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

给定一个正整数序列 $A = (A_1, A_2, \ldots, A_N)$ 。

考虑 $A$ 的所有子序列，按照成员下标区分子序列，总共有 $2^N$ 个。设这些子序列的和分别为 $S_1, S_2, \ldots, S_{2^N}$ ，并按升序排列。

对于所有满足 $1.01 \times S_k \leq S_{k+1}$ 的整数 $k$ （ $1 \leq k \leq 2^N - 1$ ），输出 $S_k, S_{k+1}, (k \bmod 998244353)$ 。

什么是子序列？一个序列 $A$ 的子序列是通过从 $A$ 中移除零个或多个元素，并保持剩余元素的原有顺序得到的序列。

输入格式

输入从标准输入读取，格式如下：

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

第一行输出满足要求的整数 $k$ 的数量。

从第二行开始，每行输出一个满足条件的 $k$ 对应的 $S_k, S_{k+1}, (k \bmod 998244353)$ ，用空格隔开。

输出需按照 $k$ 升序排列。

输入输出样例

输入#1

3
5 5 3

输出#1

输入#2
```
2
100 101
```
输出#2
```
3
0 100 1
100 101 2
101 201 3
```
输入#3
```
2
101 102
```
输出#3
```
2
0 101 1
102 203 3
```

输入#4

20
456 206 448 830 937 793 483 527 772 239 361 925 364 956 355 420 557 739 323 912

输出#4

23
0 206 1
206 239 2
239 323 3
323 355 4
355 361 5
364 420 7
420 445 8
448 456 10
456 483 11
483 527 12
529 557 14
570 594 19
594 600 20
603 626 22
626 654 23
662 678 26
695 716 32
725 733 36
743 763 39
784 793 48
820 830 60
850 865 65
11397 11603 1048575

说明/提示

样例解释 1

共有如下八个子序列：

空子序列。和为 $0$ 。
$(5)$ 。和为 $5$ 。本子序列出现两次。
$(3)$ 。和为 $3$ 。
$(5,5)$ 。和为 $10$ 。
$(5,3)$ 。和为 $8$ 。本子序列出现两次。
$(5,5,3)$ 。和为 $13$ 。

$S_1, S_2, \ldots, S_8$ 依次为 $0,3,5,5,8,8,10,13$ 。

数据范围

$2 \leq N \leq 5000$
$1 \leq A_i \leq 10^{13}$

由 ChatGPT 5 翻译

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

首页