程序设计在线评测(Online Judge)

2017年湖南科技大学大学生计算机程序设计竞赛即将于12月举行!

问题 1017. -- 2011市赛题:超炫

1017: 2011市赛题:超炫

时间限制: 1 Sec  内存限制: 128 MB
提交: 4  解决: 1
[提交][状态][讨论版]

题目描述

前阵子hh看了一系列科普片<<优雅的宇宙>>,惊讶的发现整个世界都是由弦发出不同的震动所构成的.正如优雅小提琴由几根弦就能谱出无数华美的乐章一般优雅.

弦可以十分好的解释波粒二相形,测不准原理以及真空量子涨落,同时弦又可以描述为类似橡皮筋一般的拉伸,来符合弯曲时空的相对论理论.将爱因斯坦晚年一直致力的用一组方程描述世上万力的宏愿完成了,并且将现世两大基础物理学量子力学和相对论的冲突做了完美的解释.

但是弦理论至今只停留在理论(数学计算)阶段,没办法实际的实验,因为弦是一种比夸克还小几倍的宇宙基本元素(或者说根本没有体积),为了探究宇宙的奥秘,今天我们就随hh一起根据探索弦的形态.

我们已知的条件有:

1.n*m的二维空间中存在k条弦.弦在这二维空间内不可自交.

2.弦有两种,开弦和闭弦,开弦就是一条线,闭弦是两端相连的环.

3.我们将n*m的空间分成n*m,每格占一单位面积.

4.如果在一些格子上检测到放射性标记,那么该格就不可能存在弦.

5.其他格子必然被一条且仅被一条弦占有.

6.一条弦至少占两格.

现在,让我们根据这几条信息来推测k条超弦在这二维空间内的分布情况.

输入

数据的第一行是一个数T(0<T<=100),表示接下去有T组测试数据.

每组测试数据第一行是三个整数n,m,k(0<n<=10,0<m<=7,0<=k<=5).

接下来n,每行m个字符表示二维空间内放射性标记

'.'表示该格没有放射性标记

'X'表示该格带有放射性标记

(不包含其他字符)

输出

每组测试数据输出一个整数表示k条弦在这二维空间的分布方案数(mod 10007).

Sample Input

样例输入

1
2 2 1
..
.X
2 3 2
...
...

样例输出

1
17

提示

涉及算法:连通性dp

具体看陈丹琦的论文

和一般的插头dp不同之处在于,回路和路径一起出现,不过完全理解算法后这两者还是统一的。

还有本题另外一个状态弦数K要再一个弦结尾的时候用k+1进行转移

来源

[提交][状态][讨论版]