H - Homework from Zhejiang
Editorial
/ 
/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 100 点
昨年の問題を見て，無向グラフだけでなく有向グラフの積についても勉強したパンダは，合宿で出された宿題のことを思い出しました．
問題文
M \times N 頂点の有向グラフ G が次のように与えられる．G の頂点は整数の組 (i, j) (1 \le i \le M，1 \le j \le N) で表される．G の辺は以下の通りである：
- 各 i, j, k (1 \le i, k \le M，1 \le j \le N) について，頂点 (i, j) から頂点 (k, j) へ向かう辺が A_{i,k} 本存在する．
- 各 i, j, l (1 \le i \le M，1 \le j, l \le N) について，頂点 (i, j) から頂点 (i, l) へ向かう辺が B_{j,l} 本存在する．
G の各頂点について，それを根とする全域木の個数を 998244353 で割った余りを求めよ．ただし，頂点 v を根とする全域木とは，G の辺集合の大きさ (M \times N - 1) の部分集合であって，頂点 v から他のすべての頂点へ，それらの辺を辿って到達できるようなものを指す．また，すべての辺は互いに区別できるものとする．
制約
- 2 \le M \le 500．
- 2 \le N \le 500．
- 0 \le A_{i,k} < 998244353 (1 \le i, k \le M)．
- A_{i,i} = 0 (1 \le i \le M)．
- 0 \le B_{j,l} < 998244353 (1 \le j, l \le N)．
- B_{j,j} = 0 (1 \le j \le N)．
入力
入力は以下の形式で標準入力から与えられる．
M N
A_{1,1} A_{1,2} \cdots A_{1,M}
A_{2,1} A_{2,2} \cdots A_{2,M}
\vdots
A_{M,1} A_{M,2} \cdots A_{M,M}
B_{1,1} B_{1,2} \cdots B_{1,N}
B_{2,1} B_{2,2} \cdots B_{2,N}
\vdots
B_{N,1} B_{N,2} \cdots B_{N,N}
出力
G の頂点 (i, j) を根とする全域木の個数を 998244353 で割った余りを c_{i,j} として (1 \le i \le M，1 \le j \le N)，以下の形式で出力せよ．
c_{1,1} c_{1,2} \cdots c_{1,N}
c_{2,1} c_{2,2} \cdots c_{2,N}
\vdots
c_{M,1} c_{M,2} \cdots c_{M,N}
入力例 1
2 2 0 1 0 0 0 0 1 0
出力例 1
0 2 0 0
入力例 2
3 4 0 1 1 1 0 1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0
出力例 2
5647152 5647152 5647152 5647152 5647152 5647152 5647152 5647152 5647152 5647152 5647152 5647152
入力例 3
8 7 0 135281516 667138242 534705053 894609006 363845551 983263711 368399563 706521153 0 205503439 17581194 48971395 248346723 723069160 809331769 95374102 177083480 0 966474089 652931117 138712346 184755987 158919475 378114185 853217671 858087623 0 385823507 528768155 637814125 154972838 19176284 943976794 592288689 814797836 0 36241010 768079008 314765803 951276099 885340801 394097671 282385830 497465585 0 69878345 741774067 106863220 613773019 880926179 252272587 687103226 598098347 0 464666892 209619802 423789973 917284938 456850501 156569668 254002916 550388735 0 0 374063803 312003894 140142446 439797362 925129489 698118121 224246820 0 481191147 684671827 698236806 587586359 495418696 389630714 220172615 0 865126951 43296181 113977262 779586506 686309670 840140432 20859844 0 68039199 899714832 282973414 779591352 625690436 674759197 529126191 0 797360620 123804494 621741551 994747737 802674384 746120527 131201061 0 390573239 715533801 898645859 794564126 102532744 421471382 705169995 0
出力例 3
131557205 340211781 754428084 483092626 214955141 879575978 855361045 154851590 609864261 593925945 419466834 304837127 133113507 736477090 54632615 194927386 72101830 731318386 879946775 993433194 425542545 482048637 5880376 457649402 761233161 514923047 377996184 873772583 675269156 634883332 185904773 77524684 888694113 590920163 138406866 935188259 349594389 150776180 792068517 879123091 904461829 898840329 950638863 89008070 933320378 534103502 190891412 830891397 981135229 848888881 417544354 637718293 793237398 440680172 52239789 963945205