hdu 5103 状态压缩dp

这题说的是给了n（14）个点，每个点都以他 为根的最大可容的孩子个数和最小的可溶孩子个数L[i] ,R[i]

问这n个点形成一棵树有多少种形态

我们让 dp[i][S] 表示 一 i为根节点 的 拥有孩子S（二进制数）状态的 方案数 ， sub[S] , 表示 以 S 状态表示的 森林的 方案数， sum[S] 表示 一S 状态的 有根树 的 方案数

可以知道 

dp[i][S] = sub[ S^(1<<i) ] { L[i]<=|S|<=R[i]   }

sum[S] = dp[i][S] { i=0,1,2,3,,,n-1 | S&1<<i!=0  }

sub[S] = sub[S] +  sum[H]*sub[S^H]{ H 为s 的 子集 ，然后 先固定 S 中第一个不是点 不是0 的一定要在 H 中， 这样是 为了保证 不会出现一个点被算了两次，可能这个点在枚举时存在对称性 ， 我们一旦确定一个点在那个位置就可以避免这种情况的出现 }

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
int dp[15][1<<15];
int sum[1<<15];
int sub[1<<15];
int L[15],R[15],n;
int cal(int S){
   int num=0;
   for(int i=0; i<n; ++i)
     if(S&(1<<i)) num++;
   return num;
}
int main()
{
     int cas;
     scanf("%d",&cas);
     for(int cc= 1; cc<=cas; ++cc){
         scanf("%d",&n);
         for(int i=0; i<n; ++i)
            scanf("%d%d",&L[i],&R[i]);
         for(int i=0; i<n; ++i){
             dp[i][0]=1;
         }
         sum[0]=1; sub[0]=1;
         for(int S=1; S<(1<<n); ++S){
                sum[S]=0; sub[S]=0;
              int ge = cal(S);
              for(int i =0; i<n; ++i){
                dp[i][S]=0;
                if( ( S&(1<<i) )!=0 && L[i]<=ge&&R[i]>=ge ){
                    dp[i][S]= sub[S^(1<<i)];
                    sum[S]= (dp[i][S]+sum[S])%mod;
                }
              }
              int j=0;
              for( j=0; j<n; ++j ) if(S&(1<<j)) break;

              for(int H=S; H>0; H=S&(H-1)){
                    if((H&(1<<j))==0) continue;
                    ll a = sum[H];
                    ll b = sub[S^H];
                    sub[S]= ( sub[S] + a*b%mod )%mod;
              }
         }
         int ans=0;
         for(int i=0; i<n; ++i) ans=(ans+ dp[i][(1<<n)-1])%mod;
         printf("%d
",ans);
     }

    return 0;
}