N - Product Matrix

Contest Duration: 2024-06-22(Sat) 04:00 - 2024-06-22(Sat) 09:00 (local time) (300 minutes)

N - Product Matrix Editorial

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : $100$ 点

注意

この問題の TL は厳しめに設定されています。

問題文

各要素が $1$ 次の多項式である $N$ 次正方行列 $P(x)$ が与えられます。 $P(x)$ の $(i,j)$ 成分は $a_{i,j} x + b_{i,j}$ です。

$\prod_{i=0}^{M-1} P(2^ix) = P(x) P(2x) \dots P(2^{M-1}x)$ の $(1,1)$ 成分 $f(x) = \sum_{i=0}^{M} c_ix^i$ の各係数 $c_0,c_1,\dots,c_M$ を $\bmod\ 10^9 + 7$ で求めてください。

制約

$1 \le N \le 6$
$1 \le M \le 5 \times 10^5$
$0 \le a_{i,j},b_{i,j} < 10^9 + 7$

入力

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

 $N$   $M$ 
 $a_{1,1}$   $a_{1,2}$   $\dots$   $a_{1,N}$ 
 $a_{2,1}$   $a_{2,2}$   $\dots$   $a_{2,N}$ 
 $\vdots$ 
 $a_{N,1}$   $a_{N,2}$   $\dots$   $a_{N,N}$ 
 $b_{1,1}$   $b_{1,2}$   $\dots$   $b_{1,N}$ 
 $b_{2,1}$   $b_{2,2}$   $\dots$   $b_{2,N}$ 
 $\vdots$ 
 $b_{N,1}$   $b_{N,2}$   $\dots$   $b_{N,N}$

出力

$c_0,c_1,\dots,c_M$ を $\bmod\ 10^9 + 7$ でこの順に改行区切りで出力せよ。なお、 $c_i$ は $0$ 以上 $10^9 + 7$ 未満で出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

4
8
14

$P(x)P(2x) = \begin{pmatrix} x+2 & 2x \\ 3x+1 & 4x+2 \end{pmatrix} \begin{pmatrix} 2x+2 & 4x \\ 6x+1 & 8x+2 \end{pmatrix} = \begin{pmatrix} 14x^2+8x+4 & 20x^2 + 12x \\ 30x^2+24x+4 & 44x^2+28x+4 \end{pmatrix}$ であるため、 $f(x) = 14x^2 + 8x + 4$ です。

入力例 2Copy

Copy

4 10
520471651 866160932 848899741 650346545
756377215 402412491 920748640 255249004
371442152 93295238 350011159 679848583
528399020 957465601 22001245 407745834
363922864 418156995 324388560 611306817
671914474 323815171 638034305 796072406
765823638 254662378 175686978 123364350
786531344 396717902 774813609 895184869

出力例 2Copy

Copy

入力例 3Copy

Copy

6 23
101670804 457970042 521121852 851881468 298366530 271962368
881900040 161849089 409608300 527884448 898980182 538728808
624037110 955334452 644656371 684645088 612630196 365375437
135489465 838789241 374389562 238291227 977400760 496900790
921432977 606711088 740916866 405856539 822796504 19906274
631056816 823924205 719574385 332547421 298321832 594473309
145245098 519214077 131200957 702537460 682007417 304700059
419152148 943797679 19640790 464034522 441355576 454665900
822982080 991406863 249537771 45708817 502700323 683669766
326512291 871373558 410675396 208947517 645163777 622674739
606534945 349193474 895660493 579299011 661372605 314032169
497618687 102217570 426720147 363888279 910628723 894753922

出力例 3Copy

Copy