题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3811
题意：给定1~N个数，求出至少满足一个条件的排列总数
m个条件如下：Ai 个数为Bi (0<i <m)
分析：“本意是一个复杂的容斥原理，但是开场不久被秒杀，才发现又一个比较简单的状态DP方法” 这是武大预赛解题报告上的原句。
确实，用容斥原理来解决确实十分蛋疼，最直接就是满足各个条件之后去重，好SB的样子==！。可是用状态DP却很好解决了。
我们通过求出一个条件都不满足的排列总数，从而间接的求出满足至少一个条件的排列总数。
对于当前的位置，利用前面已经求得的种数求得。
结合代码比较好解释，看代码吧 。
#include<iostream>
#include<algorithm>
using namespace std;
__int64 fact[18],dp[1<<18];
int g[18][18];
void init()
{
fact[0]=1;
for(int i=1;i<=17;i++)
fact[i]=i*fact[i-1];
}
int main()
{
int T,cas=0,n,m,a,b;
init();
scanf("%d",&T);
while(T--)
{
scanf("%d %d",&n,&m);
memset(g,0,sizeof(g));
for(int i=0;i<m;i++)
{
scanf("%d %d",&a,&b);
a--;b--;
g[a][b]=1;//标记一下，a位置不能选择b
}
memset(dp,0,sizeof(dp));
dp[0]=1;//初始化为1，
for(int i=0;i<n;i++)//枚举每一个长度
for(int j=(1<<n)-1;j>=0;j--)//枚举每一个状态，利用位运算，j的每一个位表示该数字是否已被用
{//这里注意j的枚举顺序，不能颠倒，想想为什么？
//其实从小到大枚举的话，会改掉之前所保存的值
if(dp[j]==0) continue;
for(int k=0;k<n;k++)//枚举当前位置的所有可选择的数字
{
if((j&(1<<k))!=0)//j 状态中已有了k这个数字
continue;
if(g[i][k]==1)//i位置不能选择k
continue;
dp[j|(1<<k)]+=dp[j];//j状态变成j|(1<<k)]状态产生的排列数，j|(1<<k)]状态是j状态第i+1个位置选择了k之后的状态
//状态转移，扩展序列的长度
}
}
//fact[n]表示n！，即n个数的全排列，减掉不满足条件的排列数，即为所求。
//dp[(1<<n)-1]表示不满足条件的排列总数，其中(1<<n)-1 对应的二进制每一个的前N个位均为，即该状态下n个数字都已经选择
printf("Case %d: %I64d\n",++cas,fact[n]-dp[(1<<n)-1]);
}
return 0;
}