#P1435. [ZJOI2009]多米诺骨牌

    ID: 446 传统题 1000ms 512MiB 尝试: 289 已通过: 132 难度: 9 上传者: 标签>CF2600省选/NOI-轮廓线 DP容斥原理全子集枚举线性 DP乘法原理滚动数组

[ZJOI2009]多米诺骨牌

题目描述

有一个 n×mn\times m 的矩形表格,其中有一些位置有障碍。

现在要在这个表格内放一些 1×21\times 2 或者 2×12\times 1 的多米诺骨牌,使得任何两个多米诺骨牌没有重叠部分,任何一个骨牌不能放到障碍上,并且满足任何相邻两行之间都有至少一个骨牌横跨,任何相邻两列之间也都至少有一个骨牌横跨。求有多少种不同的放置方法。

注意:你并不需要放满所有没有障碍的格子。

输入格式

第一行两个整数 n,mn,m。

接下来 nn 行,每行 mm 个字符,表示这个矩形表格。其中字符 x 表示这个位置有障碍,字符 . 表示没有障碍。

输出格式

一行一个整数,表示不同的放置方法数 mod 19901013\text{mod } 19901013 的值。

3 3
...
...
...
2

样例解释

两种放置方法分别为:

112  4.2 
411  433
4.2  332

注意这里的数字只用于区分骨牌,不同的排列并不代表不同的方案。

数据规模与约定

对于 40%40\% 的数据,满足 1≤n,m≤81\le n,m\le 8。

对于 90%90\% 的数据,满足 1≤n,m≤141\leq n,m\leq 14。

对于 100%100\% 的数据,满足 1≤n,m≤151\leq n,m \leq 15。