bzoj[1087][SCOI2005]互不侵犯King

Description

　　在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上
左下右上右下八个方向上附近的各一个格子，共8个格子。

Input

　　只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）

Output

　　方案数。

Sample Input

3 2

Sample Output

16

题解

#include<stdio.h>

int n,m;

bool st[],ts[][];

long long sum[],f[][][];

int main(){

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

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

        if(!((i>>)&i)){

            for(int x=i;x;x>>=)

                sum[i]+=x&;

            st[i]=;

        }

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

        if(!st[i])

            continue;

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

            if(st[j]&&(!(i&j))&&(!(i&(j>>)))&&(!((i>>)&j)))

                ts[i][j]=ts[j][i]=;

    }

    int c=;

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

        f[c][sum[i]][i]=;

    for(int t=;t<n;t++){

        c^=;

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

            for(int j=;j<=m;j++)

                f[c][j][i]=;

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

            if(!st[i])

                continue;

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

                if(st[j]&&ts[i][j])

                    for(int p=sum[j];p<=m-sum[i];p++)

                        f[c][p+sum[i]][i]+=f[c^][p][j];

        }

    }

    long long ans=;

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

        ans+=f[c][m][i];

    printf("%lld\n",ans);

    return ;

}