HDU 5729 Rigid Frameworks （求二分图连通方案数）

HDU 5729 Rigid Frameworks （求二分图连通方案数）

Rigid Frameworks

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 281    Accepted Submission(s): 228

Problem Description

Erik Demaine is a Professor in Computer Science at the Massachusetts Institute of Technology. Demaine's research interests range throughout algorithms, from data structures for improving web searches to the geometry of understanding how proteins fold to the computational difficulty of playing games.

Maid xiaodao is learning theoretical computer science in her spare time, and recently she was fascinated by Professor Erik Demaine's Geometric Folding Algorithms - Linkages, Origami, Polyhedra. The following problem was inspired by this book.

Recall that a graph is a collection of vertices and edges connecting the vertices, and that two vertices connected by an edge are called adjacent. Graphs can be embedded in Euclidean space by associating each vertex with a point in the Euclidean space.

Aflexible graph is an embedding of a graph where it is possible to move one or more vertices continuously so that the distance between at least two nonadjacent vertices is altered while the distances between each pair of adjacent vertices is kept constant.

⋅ Arigid graph is an embedding of a graph which is not flexible. Informally, a graph is rigid if by replacing the vertices with fully rotating hinges and the edges with rods that are unbending and inelastic, no parts of the graph can be moved independently from the rest of the graph.

Sit down and relax, to simplify the problem, let's only consider the planar graphs as grids. The grid graphs embedded in the Euclidean plane are not rigid, as the following animation demonstrates:

However, one can make them rigid by adding diagonal edges to the cells. For example, the following picture shows a 2 × 3 grid graph.

Note that you can add at most one orientation of a diagonal edge in one single cell. In fact, there are 448 ways to make a 2 × 3 grid graph rigid. And now we want to know, how many different rigid m × n grid graph with diagonal edges in total? Dear contestant, could you please find it out?

Input

There are multiple test cases. For each test case, the first line contains two integer m and n(1≤m,n≤10)

Output

For each test case, output one integer number in a single line — the number of different rigid m × n grid graph with diagonal edges. The answer could be very large, output it modulo1000000007(109+7).

Sample Input

1 23 2 7 9 10 10

Sample Output

4448 357533852 935300639

Author

HIT

Source

​​2016 Multi-University Training Contest 1​​

Recommend

wange2014   |   We have carefully selected several similar problems for you:  ​​5792​​​ ​​5790​​​ ​​5789​​​ ​​5788​​​ ​​5787​​

题意：因为矩形是不稳定的，会变成平行四边形，就像这样

，但是可以在矩形对角线加边，通过构成三角形使这个矩形稳定下来。给一n*m的矩形，可以在单位矩形里加两种对角线（从左上到右下，从左下到右上两种），或者不加对角线，或者两条。问使这个n*m的矩形稳定下来的方案数。

题解：原问题等价于求左边有n个点，右边有m个点的联通的二分图的数目 可以用类似连通图计数的方法dp得到，复杂度O(n^6)。 实际上是 projecteuler 43

那么如何计算一个二分图的连通方案数？

因为这由n*m个单位矩阵组成，每个单位矩阵可以加两种对角线（从左上到右下，从左下到右上两种），或者不加对角线，共3种选择，则一个n*m矩阵的总方案数是3^(n*m)。只要从所有方案中，除去不合法的方案数，就是合法的方案数。这么做的原因是因为不合法的方案数更容易求（只要二分图是不连通 的，这个方案就是不合法的）。

设dp[n][m]为使n*m矩阵固定下来的合法方案数。

从左边n个点中的点1固定，当连通块大小为i，j时，如何计算非法方案数，从 n-1个点中选出i-1个点（因为点1已经被固定了），从右边m个点中选出j个点，用这i，j个点组成连通块的数量就是

，i+j大小的连通块有dp[i][j]个合法的存在方案，同时，下面的 n-i 个点和 m-j 个点有

个组合方式。

做法：固定一个点，枚举这个点所处连通块的情况，只要这个连通块不包含二分图中所有的点，则当前的二分图一定是不连通的，一定是非法方案。

AC代码：

​

#includeusing namespace std;const int MAXN=40;const int mod=1e9+7;long long fact[MAXN*MAXN],C[MAXN][MAXN],dp[MAXN][MAXN];void init(){ fact[0]=1; for(int i=1;i<=110;++i) fact[i]=fact[i-1]*3%mod; C[0][0]=1; for(int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。