两个常见模型
bzoj 4321
题意：编号为1~n的人排成一排，问有多少种排法使得任意相邻两人的编号之差不为1或-1。
n<=1000
排列计数问题：考虑把数从小到大插入的过程进行dp。
设 f[i][j] 表示 1∼i 的排列，有 j 组相邻的相差1，且 i 和 i−1 不相邻的方案数；
设 g[i][j] 表示 1∼i 的排列，有 j 组相邻的相差1，且 i 和 i−1 相邻的方案数。
考虑插入i+1的位置,有4种转移方式：
1.不破坏空位且不与 i 相邻
2.不破坏空位且与 i 相邻
3.破坏空位且不与 i 相邻
4.破坏空位且与 i 相邻（只发生在 g 的转移）4种。
答案：f[n][0]
复杂度：O(n^2)
bzoj 2560
题意：有n个珠子，第i和j个珠子之间有c[i][j]条不同的绳子可选。每对珠子之间可以选择不连绳子，也可以选择用其中一种绳子连接，问有多少种方案能使n个珠子成为连通图。
n<=16
连通图计数套路：用总数减去不连通的方案数，不连通的方案数可以枚举1号点所在连通块的点集来计数。用这个点集的连通方案数乘以剩余点集的总方案数即可。
设g[s]表示s点集互相连的总方案数，f[s]表示s点集连通的总方案数。
g[s]直接预处理，从s舍弃最后一个1的点集s0转移即可，g[s]=g[s0] 累乘(c[i][j]+1)(j属于s0的任意一位1）
g预处理的复杂度:O(n*2n)
f[s]就是g[s]减去所有的不合法情况，枚举1号点所在的点集i，不合法的情况就是g[s^i]*f[i]，减去这些情况，就能求出f[s]了。
复杂度：O（3n) (枚举子集)
#include<cstdio>
using namespace std;
const int mod=1e9+7;
int c[25][25],stack[25],F[70005],G[70005],ID[70005];
int lowbit(int x){
return x&(-x);
}
int main(){
int n;
scanf("%d",&n);
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
scanf("%d",&c[i][j]);
G[0]=1;
for (int i=0; i<n; i++) ID[1<<i]=i;
for (int i=1; i<(1<<n); i++){
int top=0;
for (int j=i; j; j-=lowbit(j)) stack[++top]=ID[lowbit(j)];
G[i]=G[i-lowbit(i)];
for (int j=2; j<=top; j++) G[i]=1ll*G[i]*(c[stack[1]][stack[j]]+1)%mod;
}
for (int i=1; i<(1<<n); i++){
F[i]=G[i];
for (int j=(i-1)&i; j; j=(j-1)&i)
if (j&lowbit(i)){
F[i]-=1ll*F[j]*G[i^j]%mod;
(F[i]+=mod)%=mod;
}
}
printf("%d
",F[(1<<n)-1]);
return 0;
}