当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

5278:YJC plays automaton

题目描述
YJC is an old driver of mini train, so he was the gold medal winner of "The fatter, the better" Contest held by socks mill sesame seed bun column. An automaton caught his eye during his trip to CTSC (Consume The Special Course).

The automaton has $n+1$ states, numbered from $0$ to $n$, while $0$ represents $NULL$. So he started his study out of curiosity:

He picked out a set of start states $S$ and found some rather interesting features:

There **exists** a string $str$, satisfying that after running $str$ on each element in set $S$ you will get some final states including $NULL$ and at least one state other than $NULL$. In other words, the number of the final states $NULL$ you will get should be in the range $[1,|S|-1]$. (At least one element will be $NULL$ and at least one element won't be $NULL$)

The sets meeting these requirements are called YJC sets.

Be aware that YJC set is not allowed to include $NULL$.

He wants to know how many YJC sets there are.


If automaton is a fresh word to you, you can try to understand it this way:

An automaton has $n+1$ states, numbered from $0$ to $n$, while $0$ represents $NULL$.The size of the alphabet of the automaton is $m$.

$\delta(i,j)(0\leq i \leq n,1\leq j\leq m)$, satisfying $0\leq \delta(i,j)\leq n$ and $\delta(0,j)=0$ is called a transition function.

Here is a program explaining how a string $str$ runs on a state $t$:

$for$ $i=0..str.length-1$
$t\leftarrow \delta(t,str[i])$

If you still cannot understand how automaton works, you can turn to

https://en.wikipedia.org/wiki/Automata_theory

for further information!
输入解释
Multiple tests.

For each test:

The first line contains two integers $n,m(1\leq n\leq 888,1\leq m\leq 8)$, indicating the size of the automaton and the size of the alphabet.

The next n lines:

Each line lie $m$ elements, indicating transition function $\delta (i,j)$, the state $i$ transitions to $\delta (i,j)$ after reading the character $j$. Also, 0 represents $NULL$.
($1\leq i \leq n$ and $1\leq j \leq m$)

$NULL$ can only transitions to $NULL$.

There should be one and only one space between two integers, also, each line ends with an integer not a space. The file should end with one and only one line break.

In the final test, input file contains no more than 11000 lines. 31 groups of tests in total.

Because the final test consists of only one input file, there should be quite a lot small-range cases.

If your program can pass the largest single case within 0.5s (CPU 3.0 GHz), it shall pass the final test.
输出解释
For each test:

One line an integer $ans$, indicating the number of YJC sets.
(modulo $998244353(7\times 17\times 2^{23}+1 $ a prime$))$
输入样例
3 2
3 0
3 0
0 3
输出样例
3

提示

The possible YJC sets are $\{1,3\},\{2,3\},\{1,2,3\}$.

State $1$ is equivalent to $2$, so obviously ${1,2}$ is not a YJC set.


来自杭电HDUOJ的附加信息
Recommend hujie

该题目是Virtual Judge题目,来自 杭电HDUOJ

题目来源 BestCoder Round #46

源链接: HDU-5278

最后修改于 2020-10-25T23:21:17+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
12000/6000MS(Java/Others) 524288/262144K(Java/Others)