← 返回题目列表

AtCoder · arc210_e

E. 子集和间隙

中文机器翻译题面 查看原题

分数: 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