分数: 1000 点
问题陈述
给你一个正整数序列 A=(A_1,A_2,\ldots,A_N).
有 2^N 的子序列 A 通过子序列元素的索引来区分子序列。让 S_1, S_2, \ldots, S_{2^N} 是这些子序列的总和,枚举 按升序排列.
对于所有整数 k (1\leq k\leq 2^N-1) 满足 1.01 \times S_k\leq S_{k+1},输出 S_k, S_{k+1}, (k\bmod 998244353).
什么是子序列
序列的子序列 A 是通过从其中删除零个或多个元素获得的序列 A 并按原始顺序排列剩余元素。约束
- 2\leq N\leq 5000
- 1\leq A_i\leq 10^{13}
输入
输入由标准输入按以下格式给出:
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
5 0 3 1 3 5 2 5 8 4 8 10 6 10 13 7
我们有以下八个子序列:
- 空子序列。总和是 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
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