2015
04-13

# Permutation

In combinatorics a permutation of a set S with N elements is a listing of the elements of S in some order (each element occurring exactly once). There are N! permutations of a set which has N elements. For example, there are six permutations of the set {1,2,3}, namely [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
But Bob think that some permutations are more beautiful than others. Bob write some pairs of integers(Ai, Bi) to distinguish beautiful permutations from ordinary ones. A permutation is considered beautiful if and only if for some i the Ai-th element of it is Bi. We want to know how many permutations of set {1, 2, …., N} are beautiful.

The first line contains an integer T indicating the number of test cases.
There are two integers N and M in the first line of each test case. M lines follow, the i-th line contains two integers Ai and Bi.

Technical Specification
1. 1 <= T <= 50
2. 1 <= N <= 17
3. 1 <= M <= N*N
4. 1 <= Ai, Bi <= N

The first line contains an integer T indicating the number of test cases.
There are two integers N and M in the first line of each test case. M lines follow, the i-th line contains two integers Ai and Bi.

Technical Specification
1. 1 <= T <= 50
2. 1 <= N <= 17
3. 1 <= M <= N*N
4. 1 <= Ai, Bi <= N

3
3 2
1 1
2 1
3 2
1 1
2 2
4 3
1 1
1 2
1 3

Case 1: 4
Case 2: 3
Case 3: 18

/*

二进制DP。
第一道二进制DP，这题一段时间后要温习一下。
刚接触二进制DP，思路不是自己的，代码是看了一遍别人的思路后

自己感觉是二进制DP中的一道果题，有了二进制的思想，直接慢慢

http://qianmacao.blog.163.com/blog/static/203397180201231691849996/

还是DP好玩儿呀~

2012-11-23
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
int n,m;
__int64 fac[18];
int ban[18][18];
__int64 dp[1<<17];
void ini()
{
int i;
fac[0]=1;
for(i=1;i<=17;i++)	fac[i]=fac[i-1]*i;
}
void getban()
{
int a,b;
memset(ban,0,sizeof(ban));
while(m--)
{
scanf("%d%d",&a,&b);
a--;b--;
ban[a][b]=1;
}
}
void getdp()
{
int i,j,k;
memset(dp,0,sizeof(dp));
dp[0]=1;
for(i=0;i<n;i++)                //对位枚举
for(j=(1<<n)-1;j>=0;j--)        //注意，j的二进制位中的每一位数字表示的是：该数字是否已被用
{
if(!dp[j])	continue;
for(k=0;k<n;k++)            //当前位如果为空的情况下，枚举填入数字
{
if(j&(1<<k))	continue;   //当前位不为空
if(ban[i][k])	continue;
dp[j|(1<<k)]+=dp[j];
}
}
}
int main()
{
int T,Case;
ini();
scanf("%d",&T);
for(Case=1;Case<=T;Case++)
{
scanf("%d%d",&n,&m);
getban();
getdp();
printf("Case %d: %I64d\n",Case,fac[n]-dp[(1<<n)-1]);
}
return 0;
}