P1896 [SCOI2005] 互不侵犯

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long
int n , k ;
ll f [ 10 ] [ ( 1 << 9 ) ] [ 90 ];
int num [ ( 1 << 9 ) ] ;
int vis [ ( 1 << 9 ) ] ;
void init (  )
{
    for ( int i = 0 ; i <= ( 1 << n ) - 1  ; i ++ )
    {
        vis [ i ] = 1 ;
        if ( ( ( i << 1 ) & i ) ) vis [ i ] = 0 ;
        if ( ( ( i >> 1 ) & i ) ) vis [ i ] = 0 ;
        for ( int j = 0 ; j < n ; j ++ )
        {
            if ( ( ( i >> j ) & 1 ) == 1 )
                num [ i ] ++ ;
        }
    }
    return ;
}
bool check ( int x , int y )
{
    if ( ( x & y ) > 0 ) return false;
    if ( ( x & ( y << 1 ) ) > 0 ) return false;
    if ( ( x & ( y >> 1 ) ) > 0 ) return false;
    return true;
}
ll ans = 0 ;
int main ( )
{
    cin >> n >> k ;
    init (  ) ;
    f [ 0 ] [ 0 ] [ 0 ] = 1 ;
    for ( int i = 1 ; i <= n ; i ++ ) // 这一行
    {
        for ( int j = 0 ; j <= ( 1 << n ) - 1 ; j ++ )
        {
            if ( vis [ j ] )
            for ( int l = num [ j ] ; l <= k ; l ++ )

            for ( int k = 0 ; k <= ( 1 << n ) - 1 ; k ++ )
            {
                if ( vis [ k ] && check ( j , k ) )
                {
                    f [ i ] [ j ] [ l ] += f [ i - 1 ] [ k ] [ l - num [ j ] ] ;
                }
            }
        }
    }
    for ( int i = 0 ; i <= ( 1 << n ) - 1 ; i ++ )
        ans += f [ n ] [ i ] [ k ] ;
    cout << ans ;
    return 0 ;
}