C - Count by Descents Editorial /

Time Limit: 10 sec / Memory Limit: 2048 MiB

配点 : 1500 点

問題文

長さ N の数列 x=(x_1,x_2,\ldots,x_N) のスコアを \prod_{1 \leq i \leq N} (i+x_i) と定義します．

長さ N の狭義単調増加非負整数列 A=(A_1,A_2,\ldots,A_N) が与えられます．

各 d=0,1,\ldots,N-1 に対して以下の問題を解いてください．

  • A の要素を並び替えて得られる数列 x であって，x_i>x_{i+1} となる i がちょうど d 個あるようなものを考える．このような数列すべてに対するスコアの総和を 998244353 で割った余りを求めよ．

制約

  • 2 \leq N \leq 80
  • 0 \leq A_1 < A_2 < \cdots < A_N < 998244353
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

N
A_1 A_2 \ldots A_N

出力

各 d=0,1,\ldots,N-1 に対する答えをこの順に出力せよ．

入力例 1

2
0 1

出力例 1

3 4

各 d に対応する順列とそのスコアを以下に示します．

  • d=0:
    • x=(0,1): スコアは (1+0) \times (2+1)=3
  • d=1:
    • x=(1,0): スコアは (1+1) \times (2+0)=4

入力例 2

3
0 1 2

出力例 2

15 84 27

各 d に対応する順列とそのスコアを以下に示します．

  • d=0:
    • x=(0,1,2): スコアは (1+0) \times (2+1) \times (3+2)=15
  • d=1:
    • x=(0,2,1): スコアは (1+0) \times (2+2) \times (3+1)=16
    • x=(1,0,2): スコアは (1+1) \times (2+0) \times (3+2)=20
    • x=(1,2,0): スコアは (1+1) \times (2+2) \times (3+0)=24
    • x=(2,0,1): スコアは (1+2) \times (2+0) \times (3+1)=24
  • d=2:
    • x=(2,1,0): スコアは (1+2) \times (2+1) \times (3+0)=27

入力例 3

4
1 2 4 8

出力例 3

672 9766 11824 1350

入力例 4

10
19237225 22672563 250040585 250876592 344065186 404191279 519729086 709423541 785439575 945005786

出力例 4

950922061 100128042 407190855 824408778 310751908 135850478 488617013 247896647 212541677 410171196

入力例 5

80
22039836 28981946 30860430 45459908 69714419 80565655 86264514 88704853 91058795 111982636 139793596 151769562 164543594 197971506 210619166 221745114 225051881 238856535 245101681 248730678 255908811 256810168 272481811 273714212 283615535 284686636 297323928 298241991 319502970 321722967 360690308 361481447 366075547 418633758 422209788 423073188 433378197 437330820 459117401 480124392 485979799 486475154 490049033 498896932 504089816 518458804 520999410 531470304 542901248 560047125 582857561 595934547 619322493 622712481 627798362 686621115 695016247 712639027 714635866 721488863 735151983 742973826 753705854 758288417 768080799 775681305 834897126 851716760 855572558 858395194 905527130 907645400 908902333 922571073 933505674 948631706 966125570 978445563 979797105 985573661

出力例 5

298255098 551019397 284987769 99242062 369815630 718585554 688109983 392309922 737456536 523073775 694983953 356882261 567442787 317777842 776589570 791050897 233517530 674210008 665902332 505999118 194082824 507392235 703668642 165275650 789544696 135388036 169254144 708650783 647965741 603841383 863435804 818717034 510094830 247810285 479685478 505643001 637957324 951738617 677727811 891846762 611641571 564907071 866950984 142999964 318492053 834273618 862706905 372559206 72047272 966554479 825019950 285454795 341834405 779072147 246845153 958325353 790516997 805752624 345221877 580204783 779467953 925770800 711605667 652190020 304063629 645132429 538451131 174490604 596444184 12799293 750957647 585286962 463254142 857306647 282172657 929005032 870614339 445303380 729482922 179226742

Score : 1500 points

Problem Statement

Define the score of a sequence of length N, x=(x_1,x_2,\ldots,x_N), as \prod_{1 \leq i \leq N} (i+x_i).

You are given a strictly increasing sequence of non-negative integers of length N, A=(A_1,A_2,\ldots,A_N).

Solve the following problem for each d=0,1,\ldots,N-1.

  • Consider the sequences x obtained by rearranging the elements of A such that there are exactly d indices i with x_i>x_{i+1}. Find, modulo 998244353, the sum of the scores over all such sequences.

Constraints

  • 2 \leq N \leq 80
  • 0 \leq A_1 < A_2 < \cdots < A_N < 998244353
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

For each d=0,1,\ldots,N-1 in this order, output the answer.

Sample Input 1

2
0 1

Sample Output 1

3 4

The permutations and scores corresponding to each d are as follows.

  • d=0:
    • x=(0,1): the score is (1+0) \times (2+1)=3
  • d=1:
    • x=(1,0): the score is (1+1) \times (2+0)=4

Sample Input 2

3
0 1 2

Sample Output 2

15 84 27

The permutations and scores corresponding to each d are as follows.

  • d=0:
    • x=(0,1,2): the score is (1+0) \times (2+1) \times (3+2)=15
  • d=1:
    • x=(0,2,1): the score is (1+0) \times (2+2) \times (3+1)=16
    • x=(1,0,2): the score is (1+1) \times (2+0) \times (3+2)=20
    • x=(1,2,0): the score is (1+1) \times (2+2) \times (3+0)=24
    • x=(2,0,1): the score is (1+2) \times (2+0) \times (3+1)=24
  • d=2:
    • x=(2,1,0): the score is (1+2) \times (2+1) \times (3+0)=27

Sample Input 3

4
1 2 4 8

Sample Output 3

672 9766 11824 1350

Sample Input 4

10
19237225 22672563 250040585 250876592 344065186 404191279 519729086 709423541 785439575 945005786

Sample Output 4

950922061 100128042 407190855 824408778 310751908 135850478 488617013 247896647 212541677 410171196

Sample Input 5

80
22039836 28981946 30860430 45459908 69714419 80565655 86264514 88704853 91058795 111982636 139793596 151769562 164543594 197971506 210619166 221745114 225051881 238856535 245101681 248730678 255908811 256810168 272481811 273714212 283615535 284686636 297323928 298241991 319502970 321722967 360690308 361481447 366075547 418633758 422209788 423073188 433378197 437330820 459117401 480124392 485979799 486475154 490049033 498896932 504089816 518458804 520999410 531470304 542901248 560047125 582857561 595934547 619322493 622712481 627798362 686621115 695016247 712639027 714635866 721488863 735151983 742973826 753705854 758288417 768080799 775681305 834897126 851716760 855572558 858395194 905527130 907645400 908902333 922571073 933505674 948631706 966125570 978445563 979797105 985573661

Sample Output 5

298255098 551019397 284987769 99242062 369815630 718585554 688109983 392309922 737456536 523073775 694983953 356882261 567442787 317777842 776589570 791050897 233517530 674210008 665902332 505999118 194082824 507392235 703668642 165275650 789544696 135388036 169254144 708650783 647965741 603841383 863435804 818717034 510094830 247810285 479685478 505643001 637957324 951738617 677727811 891846762 611641571 564907071 866950984 142999964 318492053 834273618 862706905 372559206 72047272 966554479 825019950 285454795 341834405 779072147 246845153 958325353 790516997 805752624 345221877 580204783 779467953 925770800 711605667 652190020 304063629 645132429 538451131 174490604 596444184 12799293 750957647 585286962 463254142 857306647 282172657 929005032 870614339 445303380 729482922 179226742