← 返回题目列表

AtCoder · xmascon21_h

H. 浙江作业

中文机器翻译题面 查看原题

配点 : 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