/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 1000 点
問題文
正整数列 A=(A_1,A_2,\ldots,A_N) が与えられます．
A の部分列は，要素の添字の違いを区別すれば，2^N 個あります．これらの各部分列の総和を昇順に列挙したものを，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 の要素を 0 個以上選んで削除し，残った要素を元の順序を保って並べた数列のことを指します．制約
- 2\leq N\leq 5000
- 1\leq A_i\leq 10^{13}
入力
入力は以下の形式で標準入力から与えられます．
N A_1 A_2 \ldots A_N
出力
1 行目には，条件を満たす整数 k の個数を出力してください．
2 行目以降には各行に，条件を満たす整数 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
部分列は次の 8 個です．
- 空な部分列．総和は 0 である．
- (5)．総和は 5 である．この部分列は 2 回現れる．
- (3)．総和は 3 である．
- (5,5)．総和は 10 である．
- (5,3)．総和は 8 である．この部分列は 2 回現れる．
- (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
Score : 1000 points
Problem Statement
You are given a sequence of positive integers A=(A_1,A_2,\ldots,A_N).
There are 2^N subsequences of A when distinguishing subsequences by the indices of their elements. Let S_1, S_2, \ldots, S_{2^N} be the sums of these subsequences, enumerated in ascending order.
For all integers k (1\leq k\leq 2^N-1) that satisfy 1.01 \times S_k\leq S_{k+1}, output S_k, S_{k+1}, (k\bmod 998244353).
What is a subsequence
A subsequence of a sequence A is a sequence obtained by removing zero or more elements from A and arranging the remaining elements in their original order.Constraints
- 2\leq N\leq 5000
- 1\leq A_i\leq 10^{13}
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
On the first line, output the number of integers k that satisfy the condition.
From the second line onwards, for each integer k that satisfies the condition, output S_k, S_{k+1}, (k\bmod 998244353) separated by spaces on each line.
Output in ascending order of k.
Sample Input 1
3 5 5 3
Sample Output 1
5 0 3 1 3 5 2 5 8 4 8 10 6 10 13 7
We have the following eight subsequences:
- The empty subsequence. The sum is 0.
- (5). The sum is 5. This subsequence appears twice.
- (3). The sum is 3.
- (5,5). The sum is 10.
- (5,3). The sum is 8. This subsequence appears twice.
- (5,5,3). The sum is 13.
S_1, S_2, \ldots, S_8 are 0,3,5,5,8,8,10,13 in order.
Sample Input 2
2 100 101
Sample Output 2
3 0 100 1 100 101 2 101 201 3
Sample Input 3
2 101 102
Sample Output 3
2 0 101 1 102 203 3
Sample Input 4
20 456 206 448 830 937 793 483 527 772 239 361 925 364 956 355 420 557 739 323 912
Sample Output 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