UOJ Logo Universal Online Judge

UOJ

#76. 【UR #6】懒癌

附件下载 统计

你绞尽脑汁也没有解开智商锁给的迷题,只见哐地一下门就开了:“您与锁的主人智商一致。”

于是你们窃取了大量内部资料,最后端掉了 IIIS。

但是,虽然 IIIS 被摧毁了,当地居民仍有大量在星期八休息的,而且看不惯在星期日休息的人,在星期日休息的人同样看不惯在星期八休息的人,于是整个社会秩序被打乱得一塌糊涂。

当地共有 $2^n - 1$ 个村庄,每个村庄住着 $n$ 户人家,门牌号分别为 $1, 2, \dots, n$,每户人家家里养着一条狗。恰逢无药可治的懒癌流行,人人自危。每个村庄都有至少一只狗得了懒癌。一个村庄中,门牌号为 $i$ 的人家的狗要么得懒癌,要么不得懒癌,一共 $2^n$ 种情况,再去掉都没得懒癌的情况,一共 $2^n - 1$ 种。这每种情况都会发生在恰好一个村庄中。

这天来了个善良的人来到每个村庄中,告诉所有人一个爆炸性的新闻:“你们村里至少有一只狗得了懒癌!”

每个村庄中每户人家都不知道自己的狗到底是懒癌还是可爱,但是他能一眼看出某些人家的狗有没有得懒癌。由于这个社会里人与人之间的信任已经崩塌,一个人即使看出别人的狗是否得懒癌也不愿告诉他。

可以用一个 $n$ 个结点的有向图来描述可见性,$v$ 到 $u$ 有一条有向边表示门牌号为 $v$ 的人家能看出门牌号为 $u$ 的家里的狗是否得了懒癌,没边则表示看不出。每个人都知道这张有向图。

于是一个残酷的逻辑链条开始启动。对于每个村庄:

  1. 第一天,早上每户人家的主人会出门看看别人家的狗,如果一个人能推断出自己家的狗得了懒癌,下午6点整,他就会掏出手枪一枪把自己家的狗毙了。
  2. 如果有多个人都在同一天推断出了,那么他们会在下午6点整同时开枪。
  3. 每个人都听得到这个村庄里的枪声。如果没有听到枪声,这个村里的人第二天会继续早上出门看狗,推断出自己家狗得了懒癌下午就杀狗。如果还没有听到枪声,第三天也会如此,依次类推。(所以如果一个人听到了枪声那么就不会再开枪杀狗)

作为一个想帮助当地居民调节矛盾的你想要向当地居民展示灾难性的后果,请计算出对于所有前 $233^n$ 天内有过枪声的村庄

  1. 开枪时间之和。如一个村庄在第 $k$ 天下午响起枪声,则开枪时间为 $k$。(多个人同时开枪只算一次)
  2. 死亡的狗的总数。

你只用输出对 $998244353$($7 \times 17 \times 2^{23} + 1$,一个质数)取模后的结果。

输入格式

第一行一个整数 $n$,含义如前所述。

接下来 $n$ 行每行 $n$ 个字符,表示可见性。这 $n$ 行中的第 $v$ 行第 $u$ 个字符为 “1” 表示 $v$ 能看出 $u$ 家的狗是否得懒癌,如果字符为 “0” 表示看不出。保证只会出现 “0” 和 “1” 这两种字符,且对于任意一个满足 $1 \leq v \leq n$ 的 $v$,第 $v$ 行第 $v$ 列为 “0”。

输出格式

一行输出两个整数分别表示开枪时间和、死亡的狗的总数。

样例一

input

2
01
00

output

5 3

explanation

门牌号为 1 的人能看见门牌号为 2 的人家里的狗是不是病狗。

共有三个村庄。

  1. 1 病了,2 没病。第一天 1 发现 2 没得病,又知道他们中肯定有一个病了,所以第一天下午开枪杀了狗。开枪时间为 $1$,死了 $1$ 只狗。
  2. 1 没病,2 病了。第一天 1 发现 2 得了病,于是第一天两个人什么也没干。第二天 2 发现前一天 1 没有开枪,所以下午开枪杀了狗。开枪时间为 $2$,死了 $1$ 只狗。
  3. 1 病了,2 病了。2 还是第二天开枪杀了狗,1 始终没有开枪。开枪时间为 $2$,死了 $1$ 只狗。

所以 $1 + 2 + 2 = 5$,$1 + 1 + 1 = 3$。

样例二

input

2
01
10

output

4 4

explanation

理由类似样例一。

样例三

见样例数据下载。

限制与约定

测试点编号 $n$的规模 其它限制
1$n \leq 8$
2
3$n \leq 20$
4
5$n \leq 100$
6
7$n \leq 3000$每户人家都能看出其他每户人家的狗有没有得懒癌
8
9
10

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

后记

你成功帮他们调解了矛盾,最后当地居民决定每周星期七点五为休息日,即星期日下午到星期八早上。

下载

样例数据下载