bzoj1087互不侵犯King（状压）

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1087

简单的状压dp。但是wa了好几发。注意long long。

注意0和0的连边。而且不能连成两条，所以放在外面写。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=,M=<<;

int n,m,lm,list[M+][M+],cnt[M+],zt[M+],xnt,nm[M+];//那一维是N*N！

long long ans,dp[N][N*N][M+];//

int num(int s)

{

    int cnt=;

    while(s)cnt++,s-=(s&-s);

    return cnt;

}

void init()

{

    lm=(<<n);

    for(int s=;s<lm;s++)

        if(((s<<)&s)==)

        {

            zt[++xnt]=s;

            nm[xnt]=num(s);

        }

    list[][++cnt[]]=;

    for(int i=;i<=xnt;i++)

        for(int j=i+;j<=xnt;j++)

            if(((zt[i]<<)&zt[j])==&&((zt[i]>>)&zt[j])==&&(zt[i]&zt[j])==)

                list[i][++cnt[i]]=j,list[j][++cnt[j]]=i;

}

int main()

{

    scanf("%d%d",&n,&m);

    init();

    for(int i=;i<=xnt;i++)dp[][nm[i]][i]=;

    for(int i=;i<=n;i++)

        for(int s=;s<=xnt;s++)

            for(int j=nm[s];j<=m;j++)

                for(int k=;k<=cnt[s];k++)

                    dp[i][j][s]+=dp[i-][j-nm[s]][list[s][k]];

//                        printf("dp[%d][%d][%d]=%d(dp[%d][%d][%d]=%d) %d %d\n",i,j,s,dp[i][j][s],

//                                i-1,j-nm[s],list[s][k],dp[i-1][j-nm[s]][list[s][k]],zt[s],zt[list[s][k]]);

    for(int i=;i<=xnt;i++)ans+=dp[n][m][i];

    printf("%lld",ans);

    return ;

}