【问题描述】

一个图被认为是刚体，如果该图无法只改变其中一部分的形状，而使得余下的部分的形状保持不变。

例如上图中的 (a) (b) (c) 都是刚体。

为了简化问题，我们现在只考虑 n × m 的格点图。

上图不是刚体，但是可以通过在对角线加入支撑的方式使得其变为刚体。

我们的问题是，对于 m × n 的个点图，有多少种添加支撑的方案可以使其变为刚体？

注意本题在每个小矩形中，我们至多只允许添加一个方向的对角线。

例如，对于 2 × 3 的格点图，一共有 448 种方案。

【输入格式】

从文件 graph.in 中读入数据.

\(T\)

\(n_1\) \(m_1\)

\(\vdots\)

\(n_T\) \(m_T\)

【输出格式】

输出到文件 graph.out 中.

输出共 T 个整数,表示方案数。

【样例输入】

4

1 2

3 2

7 9

10 10

【样例输出】

4

448

357533852

935300639

【子任务】

对于 20% 的数据 n ≤ 4, m ≤ 4

对于另 20% 的数据 n = 1 或 m = 1

对于另 20% 的数据 n ≤ 10, m ≤ 10

对于另 20% 的数据 n ≤ 30, m ≤ 30

对于 100% 的数据 n ≤ 100, m ≤ 100, T ≤ 5

【正解】

一开始我们会认为只要每行每列存在至少一个支架就能够支撑，但其实是不对的

我们把最开始的图看作是一团乱麻，不要看作是规则的。然后我们每加入一个支架，就是使一行的竖边和一列的横边垂直。我们最后需要的状态是所有竖边和横边垂直

在最开始的想法中，虽然每行每列都有垂直，但是有可能是错开的扭曲的垂直

回到思路上来，考虑建出一个二分图\(G_{n,m}\)，答案就是使得二分图\(G_{n,m}\)联通的方案数

再设计dp

\(f[i][j]\)表示\(G_{i,j}\)的联通方案数

转移方程：

\[f[i][j]=3^{ij}-\sum_{k=1}^i\sum_{l=0}^jC_{i-1}^{k-1}C_{j}^{l}f[k][l]3^{(i-k)(j-l)}\]

\(3^{ij}\)是二分图所有情况的总数，再算出不合法情况，进行容斥

考虑枚举一号点所在联通块大小

\(\sum_{k=1}^i\)是在枚举左边部分\(i\)个点包括一号点在内总共有\(k\)个点与一号点联通

\(\sum_{l=0}^j\)则是在枚举右边

\(C_{i-1}^{k-1}C_{j}^{l}\)是指左边要有\(k\)个点，那么要从二号点到\(i\)号点中选\(k-1\)个点出来，右边同理

\(3^{(i-k)(j-l)}\)是因为我们保证了一号点所在的联通块不会再和其他点联通，所以剩下的点随便怎么连，总共有\(3^{(i-k)(j-l)}\)方案数

这样转移，还要注意一些小细节，要预处理组合数，预处理3的幂

#include
    
     #define ll long longconst int Mod=1e9+7,MAXN=100+10;int T;ll f[MAXN][MAXN],C[MAXN][MAXN],exp3[MAXN*MAXN];template
     
       inline void read(T &x){    T data=0,w=1;    char ch=0;    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();    if(ch=='-')w=-1,ch=getchar();    while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();    x=data*w;}template
      
        inline void write(T x,char c='\0'){    if(x<0)putchar('-'),x=-x;    if(x>9)write(x/10);    putchar(x%10+'0');    if(c!='\0')putchar(c);}template
       
         inline void chkmin(T &x,T y){x=(y
        
         
           inline void chkmax(T &x,T y){x=(y>x?y:x);}template
          
            inline T min(T x,T y){return x
           
            
              inline T max(T x,T y){return x>y?x:y;}inline ll qexp(ll a,ll b){ ll res=1; while(b) { if(b&1)res=res*a%Mod; a=a*a%Mod; b>>=1; } return res;}inline void init(){ exp3[0]=1; for(register int i=1;i