hdu3811 Permutation(상태 압축 DP)

제목은 내가 누르고 내가 누르는 제목의 대의: 제목은 m대 ab를 제시하고 a의 위치를 b로 표시한다. 그 중에서 적어도 한 쌍의 관계의 총 배열수를 만족시키라고 묻는다.
사고방식: 표면적으로 보면 정리를 용납하는 것 같지만 될지 안 될지 나도 시도해 본 적이 없다. 상태로 DP를 압축하면 매우 빠르다. dp[i]는 제i종의 상태가 a위치에서 b를 놓는 상황에 부합되지 않는 숫자를 기록한다. dp[(1<<

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define inf 0x3f3f3f3f
long long dp[1<<18];
long long per[18]={0, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000};
//    N  N！     ， N！   a 
int flag[18][18];
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int t,n,m,a,b,cas=1;
    scanf("%d",&t);
    while(t--)
    {
        memset(dp,0,sizeof(dp));
        memset(flag,0,sizeof(flag));
        scanf("%d%d",&n,&m);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            a--;b--;
            flag[a][b]=1;    // flag  a      b
        }
        dp[0]=1;
        for(int i=0;i<n;i++)
        {
            for(int j=(1<<n)-1;j>=0;j--)
            {
                if(!dp[j])continue;
                for(int k=0;k<n;k++)
                {
                    if((j&(1<<k))!=0)continue; //j      k 
                    if(flag[i][k]==1)continue; //k     i
                    dp[j|(1<<k)]+=dp[j];
                }
            }
        }
        printf("Case %d: %lld
",cas++,per[n]-dp[(1<<n)-1]);
    }
    return 0;
}