AT_xmascon21_h.Homework from Zhejiang

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个 $M \times N$ 个顶点的有向图 $G$ ，定义如下。 $G$ 的顶点由整数对 $(i, j)$ 表示（ $1 \leq i \leq M$ ， $1 \leq j \leq N$ ）。 $G$ 的边如下：

对于每个 $i, j, k$ （ $1 \leq i, k \leq M$ ， $1 \leq j \leq N$ ），从顶点 $(i, j)$ 到顶点 $(k, j)$ 有 $A_{i,k}$ 条有向边。
对于每个 $i, j, l$ （ $1 \leq i \leq M$ ， $1 \leq j, l \leq N$ ），从顶点 $(i, j)$ 到顶点 $(i, l)$ 有 $B_{j,l}$ 条有向边。

请对于 $G$ 的每个顶点，求以该顶点为根的全域树（即生成树）的个数对 $998244353$ 取模的结果。这里，以顶点 $v$ 为根的全域树指的是， $G$ 的边集合的一个大小为 $M \times N - 1$ 的子集，使得从顶点 $v$ 出发，能够通过这些边到达所有其他顶点。注意，所有的边都是互相区分的。

输入格式

输入通过标准输入给出，格式如下：

$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 \leq i \leq M$ ， $1 \leq j \leq 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

输出#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

说明/提示

限制条件

$2 \leq M \leq 500$ 。
$2 \leq N \leq 500$ 。
$0 \leq A_{i,k} < 998244353$ （ $1 \leq i, k \leq M$ ）。
$A_{i,i} = 0$ （ $1 \leq i \leq M$ ）。
$0 \leq B_{j,l} < 998244353$ （ $1 \leq j, l \leq N$ ）。
$B_{j,j} = 0$ （ $1 \leq j \leq N$ ）。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页