QOJ.ac

QOJ

Time Limit: 1.5 s Memory Limit: 512 MB Total points: 100 Difficulty: [show]

#7989. 三染色

統計

题目描述

我有一个调色盘,总共 $n$ 行 $m$ 列,形成了 $n\times m$ 个格子,每个格子里要放一朵花。可以放置的花有 $3$ 种颜色可以选择,分别用 $0,1,2$ 表示。

花朵注视着它周围的花,并想要变成其他花朵的样子。如果在一个时刻,一朵颜色为 $c$ 的花的上、下、左、右之一,有至少一朵花的颜色为 $c-1$,那么这朵花在下一个时刻会变成颜色 $c-1$,否则它在下一个时刻的颜色仍然是 $c$。其中颜色 $\bmod 3$ 考虑。

对于一个初始的在调色盘中放花的方案,如果经过有限个时刻之后,所有花都变成同一颜色,我们称这个放花的方案是美好的

不难看出,对于一个美好的放花方案,每朵花都有一个最早的时刻,它在这个时刻之后一直不变色。我们称这个时刻为这朵花的稳定时刻。 我们从第 $0$ 时刻开始计时,所以一朵花如果从未改变颜色,那么它的稳定时刻就是 $0$。

现在我已经在调色盘的一些格子中放置了花朵,也有一些格子是空的。我想知道,有多少种给剩余的格子放花的方案,使得这个方案是美好的?以及,对于这些美好的方案,位于第 1 行第 1 列格子中花朵的稳定时刻的总和是多少?

你只需要回答我这两个结果对 $998244353$ 取模的值。

输入格式

从标准输入读入数据。

输入第一行为两个正整数 $n,m$($2 \le n \le 5$,$2 \le m \le 50$)。

接下来 $n$ 行,每一行 $m$ 个整数,第 $i$ 行第 $j$ 个整数 $a_{i,j}\in \{0,1,2,3\}$ 表示对应方格的状态。其中 $a_{i,j}\in \{0,1,2\}$ 表示有一朵花,以及这朵花的颜色,$a_{i,j}=3$ 表示没有花。

输出格式

输出到标准输出。

输出一行两个整数,表示美好的方案数,和左上角格子中花朵稳定时刻的总和。

样例

输入

2 2
1 0
3 2

输出

1 2

解释

只有在未知格子放入花朵颜色为 $0$ 的时候会结束,并且在两个时刻之后所有花朵的颜色全部变为 $2$,此时左上角方格中的花朵颜色变成 $2$ 并不再改变,因此它的稳定时刻就是 $2$。

样例

输入

5 5 
3 3 3 3 2
2 3 3 3 1
1 3 3 3 3
3 3 3 3 3
3 3 3 3 3

输出

50830224 170059345
About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

  1. This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
  2. Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
  3. Issues must be filed in English or Chinese only.
  4. Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0

No issues in this category.