|
Description
有一个n×m的矩形表格，其中有一些位置有障碍。现在要在这个表格内放一些1×2或者2×1的多米诺骨牌，使得任何两个多米诺骨牌没有重叠部分，任何一个骨牌不能放到障碍上。并且满足任何相邻两行之间都有至少一个骨牌横跨，任何相邻两列之间也都至少有一个骨牌横跨。求有多少种不同的放置方法，注意你并不需要放满所有没有障碍的格子。
Input
第一行两个整数n;m。接下来n 行，每行m 个字符，表示这个矩形表格。其中字符“x” 表示这个位置有障碍，字符“.” 表示没有障碍。
Output
一行一个整数，表示不同的放置方法数mod 19901013 的值。
Sample Input
3 3
...
...
...
Sample Output
2
Hint
两种放置方法分别为
112 411
4.2 4.2
433 332
注意这里的数字只用于区分骨牌，不同的排列并不代表不同的方案。
【数据范围】
对于40% 的数据，满足1 ≤ n;m ≤ 8。
对于90% 的数据，满足1 ≤ n;m ≤ 14。
对于100% 的数据，满足1 ≤ n;m ≤ 15。
被这道题虐了一上午…… 首先考虑一个更简单一些的情况： 若没有“任何相邻两行、列之间都至少有一个骨牌横跨”的限制，那么问题就相当简单了（直接一个裸的状压DP就好了）； 若只有行（任意两行之间）的跨立没有列的跨立，当然也很简单（用插头DP实现，保证每行结束都至少有一个插头指向下一行）。 再回到原问题中。 一种想法就是增加状态的信息，在转移的时候将相邻各列的相连情况记录下来，解决了列的横跨问题；并且用上面所说的方法解决行的横跨问题。（下面附代码。）这样做的复杂度是O(n·m·4^m)，显然要超时。 所以需要继续寻找其他办法。 通常，我们很容易计算某两行（列）之间一定没有骨牌横跨的情况（只需把原问题分解为几个小的部分再把分别的结果相乘即可），所以这令人想到了容斥原理！ 首先一个预处理（用状压DP实现），算出ini[U][D][L][R]即在U |