#1944. 小Z的礼物
小Z的礼物
小Z的礼物
题目描述
标题: 小Z的礼物 - Problem - QOJ.ac
#13622. 小Z的礼物
小Z有一个神奇的自动售货机,里面有 n×m 种物品,分别放在 n 行 m 列个格子中。每当小Z向自动售货机中投入一枚硬币,他就能获得一对相邻格子中的物品(已经获得的物品可能再次获得),获得每一对相邻格子中的物品的概率是相等的。在这 n×m 种物品中,有一些物品是小Z喜欢的(小Z喜欢的用 * [星号] 表示,其他的用 .[英文句号] 表示),他想把这些物品包装成一份礼物。小Z想知道,期望投入多少枚硬币后,就可以获得这些他喜欢的物品。
输入格式
第一行两个整数 n 和 m。
接下来 n 行,每行一个长度为 m 的字符串,字符串中仅包含 * 和 . 两种字符。
输出格式
一个整数,表示在模 998244353 意义下的答案。
样例一
input
1 3
***
output
3
样例二
input
3 3
..*
*.*
.*.
output
404051295
限制和约定
对于所有数据,保证 1≤n≤6,2≤m≤100。
本题使用捆绑测试。每个子任务有若干个测试点,分为 5 个子任务,你只有通过一个子任务的所有测试点才能得到这个子任务的分数。
为方便表示,设 cnt 为输入中 * 的数量, s 为由 * 组成的最大连通块(四连通)的大小。
子任务分值限制 110cnt≤6 220cnt≤20 320s≤1 420s≤16 530无特殊限制
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
1 3
***
3
样例 2
3 3
..*
*.*
.*.
404051295