分数: 1200 点
问题陈述
你被给予 N \times N 整数矩阵 A = (A_{i,j})_{1 \leq i \leq N, 1 \leq j \leq N} 和一个整数 M.
对于整数序列 x = (x_1, x_2, \cdots, x_M) 长度 M 由之间的整数组成 1 和 N,包含,定义 f(x) 如下:
- 让 y = (y_1, y_2, \cdots, y_M) 是通过对元素进行排序获得的序列 x 为非递减。
- 定义 f(x) = \prod_{1 \leq i \leq M} A_{x_i, y_i}.
对于每个 k = 1, 2, \cdots, N,解决以下问题:
- 求总和 f(x) 所有序列 x 满意 x_1 = k,模数 998244353.
约束
- 1 \leq N \leq 50
- 1 \leq M \leq 50
- 0 \leq A_{i,j} < 998244353
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M
A_{1,1} A_{1,2} \cdots A_{1,N}
A_{2,1} A_{2,2} \cdots A_{2,N}
\vdots
A_{N,1} A_{N,2} \cdots A_{N,N}
输出
打印每个问题的答案 k = 1, 2, \cdots, N 按此顺序。
示例输入 1
2 2 1 2 3 4
示例输出 1
5 22
一切皆有可能 x 以及相应的值 f(x) 如下。
- x = (1, 1): y = (1, 1), f(x) = A_{1,1} \times A_{1,1} = 1
- x = (1, 2): y = (1, 2), f(x) = A_{1,1} \times A_{2,2} = 4
- x = (2, 1): y = (1, 2), f(x) = A_{2,1} \times A_{1,2} = 6
- x = (2, 2): y = (2, 2), f(x) = A_{2,2} \times A_{2,2} = 16
因此,答案是 1 + 4 = 5 为 k = 1,和 6 + 16 = 22 为 k = 2.
示例输入 2
2 3 1 2 3 4
示例输出 2
27 118
示例输入 3
5 4 785439575 250040585 709423541 945005786 19237225 404191279 250876592 22672563 519729086 344065186 273714212 560047125 139793596 542901248 520999410 855572558 498896932 418633758 742973826 248730678 238856535 319502970 908902333 164543594 245101681
示例输出 3
216530400 726773157 717209375 797938347 957133905
示例输入 4
10 50 197971506 714635866 966125570 768080799 80565655 459117401 256810168 775681305 582857561 948631706 437330820 321722967 531470304 255908811 45459908 504089816 695016247 91058795 905527130 30860430 151769562 979797105 619322493 298241991 360690308 480124392 297323928 284686636 922571073 627798362 753705854 712639027 721488863 69714419 485979799 88704853 758288417 423073188 595934547 86264514 272481811 622712481 221745114 225051881 433378197 985573661 210619166 851716760 283615535 834897126 366075547 933505674 858395194 490049033 22039836 361481447 735151983 518458804 422209788 28981946 907645400 111982636 978445563 686621115 486475154 734616351 587635888 527524079 454844580 826849288 868863954 490627044 967828344 887235558 138021910 435784230 343307056 118718683 547282350 757693154 32344652 101428952 585897722 693817619 790433406 848494439 873744405 604427602 951889915 989125209 865548541 642980476 603592935 911086893 466178404 79002814 902745597 825893950 147052664 805753279
示例输出 4
862518623 606960987 762676180 606184511 762408948 47716007 968649097 788324707 140177479 484063588