#1944. 小Z的礼物

    ID: 1944 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest2398来源:qoj.ac数据:公开样例最短路数学

小Z的礼物

小Z的礼物

题目描述

标题: 小Z的礼物 - Problem - QOJ.ac

#13622. 小Z的礼物

Statistics

小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