题意：给一些人的排列限制关系（比如x要排在y前面），求符合这些条件的排列总数。
分析: 这题自己没想出来，看了别人的题解。这句“我们想求一堆人的排列总数，它等于在这一堆人中减去每一个入度为 0 的人，剩下的人的排列总数的和。”就是这题的方法了。记忆化搜索写法。
 
#include <iostream>
#include <memory.h>
#include <stdio.h>
#include <cstring>
using namespace std;
#define LL long long

LL dp[(1<<16)+10],g[16][16],din[16],n,m;
char name[16][20];

LL find(char s[])
{
    for(LL i=0;i<=n;i++)
    {
        if(strcmp(s,name[i])==0) return i;
    }
    return -1;
}

LL dfs(LL now)
{
    LL i,j;
    if(dp[now]>=0) return dp[now];
    dp[now]=0;
    for(i=0;i<n;i++)
    {
        if(!din[i]&&(now&(1<<i))) // 如果i的入度为0且now这个状态含有i
        {
            for(j=0;j<n;j++)
            {
                if(g[i][j]) din[j]--;
            }
            dp[now]+=dfs(now-(1<<i));   // 递推关系
            for(j=0;j<n;j++)   // 恢复
            {
                if(g[i][j]) din[j]++;
            }
        }
    }
    return dp[now];
}

int main()
{
    LL i,x,y,ans,nmax,j;
    char s1[20],s2[20];
    while(scanf("%lld",&m)!=EOF)
    {
        memset(g,0,sizeof(g));
        n=-1;
        for(i=1;i<=m;i++)
        {
            scanf("%s %s",s1,s2);
            x=find(s1);
            if(x==-1) {strcpy(name[++n],s1); x=n;}
            y=find(s2);
            if(y==-1) {strcpy(name[++n],s2); y=n;}
            g[x][y]=1;
        }
        n++;
        memset(din,0,sizeof(din));
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                if(g[i][j]) din[j]++;
            }
        }
        memset(dp,-1,sizeof(dp));
        for(i=0;i<n;i++) dp[(1<<i)]=1;   // 只剩一个人的时，必然是1 所以先设好边界
        nmax=(1<<n)-1;
        ans=dfs(nmax);
        printf("%lld\n",ans);
    }
    return 0;
}