Description

你突然有了一個(gè)大房子，房子里面有一些房間。事實(shí)上，你的房子可以看做是一個(gè)包含n*m個(gè)格子的格狀矩形，每個(gè)格子是一個(gè)房間或者是一個(gè)柱子。在一開始的時(shí)候，相鄰的格子之間都有墻隔著。 你想要打通一些相鄰房間的墻，使得所有房間能夠互相到達(dá)。在此過程中，你不能把房子給打穿，或者打通柱子（以及柱子旁邊的墻）。同時(shí)，你不希望在房子中有小偷的時(shí)候會(huì)很難抓，所以你希望任意兩個(gè)房間之間都只有一條通路。現(xiàn)在，你希望統(tǒng)計(jì)一共有多少種可行的方案。 Input

第一行兩個(gè)數(shù)分別表示n和m。 接下來n行，每行m個(gè)字符，每個(gè)字符都會(huì)是’.’或者’’，其中’.’代表房間，’’代表柱子。 Output

一行一個(gè)整數(shù)，表示合法的方案數(shù) Mod 10^9 Sample Input 3 3

…

…

.*.

Sample Output 15 HINT

對(duì)于前100%的數(shù)據(jù)，n,m<=9

解法：Matrix-Tree就是生成樹計(jì)數(shù)問題的計(jì)算方法，不知道可以百度，推導(dǎo)我忘得差不多了，隊(duì)友說記得結(jié)論就可以了，那好吧。。。。所以這道題就轉(zhuǎn)化了一個(gè)行列式求值的問題，但是我們不能直接高斯消元，這是整數(shù)，顯然精度是會(huì)boom的對(duì)吧。那么怎么做呢？我也不會(huì)啊，看了hzwer的一種利用輾轉(zhuǎn)相除法來計(jì)算的姿勢，很棒棒啊。大概是這樣的，高斯消元時(shí)進(jìn)行初等變換，正常高斯消元把某行乘以某個(gè)數(shù)字加到另一行上，使得目標(biāo)行某個(gè)位置為0，算出對(duì)應(yīng)位置比例一次變換。在整數(shù)意義下，設(shè)對(duì)應(yīng)位置數(shù)值為b，a使得a為0，則使a所在行+b所在行*a/b，(b,a)->(b,a mod b)。交換2行，做類似相同操作，直到b或a為0停止。