hdu5731

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 const int mo=1e9+7;
 5 int n,m;
 6 int ans[20][20],f[20][20],s[20],g[20],q[20];
 7 void inc(int &a,int b)
 8 {
 9     a+=b;
10     if (a>=mo) a-=mo;
11 }
12 struct node
13 {
14     int st[1<<16],f[1<<16],len;
15     void clr()
16     {
17         for (int i=1; i<=len; i++) f[st[i]]=0;
18         len=0;
19     }
20     void push(int nw,int w)
21     {
22         if (f[nw]==0) st[++len]=nw;
23         inc(f[nw],w);
24     }
25  } h[2];
26 
27  void get()
28  {
29      for (int m=1; m<=16; m++)
30      {
31          int p=0; h[1].clr(); h[0].clr();
32          h[0].push(0,1);
33          for (int i=1; i<=16; i++)
34          {
35             for (int j=0; j<m; j++)
36             {
37                 p^=1; h[p].clr();
38                 for (int k=1; k<=h[p^1].len; k++)
39                 {
40                     int st=h[p^1].st[k];
41                     int w=h[p^1].f[st];
42                     if (i==1)
43                     {
44                         if (j&&!(st>>(j-1)&1)) h[p].push(st|(1<<(j-1))|(1<<j),w);
45                         h[p].push(st,w);
46                     }
47                     else if (st>>j&1)
48                     {
49                         if (j&&!(st>>(j-1)&1)) h[p].push(st|(1<<(j-1)),w);
50                         h[p].push(st^(1<<j),w);
51                     }
52                     else h[p].push(st|(1<<j),w);
53                 }
54             }
55             f[i][m]=h[p].f[(1<<m)-1];
56          }
57      }
58  }
59 
60 void calc()
61 {
62     memset(ans,0,sizeof(ans));
63     for (m=1; m<=16; m++)
64     {
65         for (int st=0; st<1<<(m-1); st++)
66         {
67             int t=0;
68             for (int k=0; k<m-1; k++)
69                 if (st>>k&1) q[++t]=k+1;
70             q[t+1]=m;
71             for (int i=1; i<=16; i++)
72             {
73                 s[i]=1;
74                 for (int j=1; j<=t+1; j++)
75                     s[i]=1ll*s[i]*f[i][q[j]-q[j-1]]%mo;
76             }
77             for (int i=1; i<=16; i++)
78             {
79                 g[i]=s[i];
80                 for (int j=1; j<i; j++)
81                     inc(g[i],mo-1ll*s[i-j]*g[j]%mo);
82                 if (t&1) inc(ans[i][m],mo-g[i]);
83                 else inc(ans[i][m],g[i]);
84             }
85         }
86     }
87 }
88 
89 int main()
90 {
91     get();
92     calc();
93     while (scanf("%d%d",&n,&m)!=EOF) printf("%d\n",ans[n][m]);
94 }