首页 > 代码库 > ZOJ 3687 The Review Plan I ( 禁位排列 + 容斥原理 )

ZOJ 3687 The Review Plan I ( 禁位排列 + 容斥原理 )

 

ZOJ 3687 The Review Plan I ( 禁位排列 + 容斥原理 )

 

 

 

 

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long LL;#define CLR( a, b ) memset( a, b, sizeof(a) )#define MOD 55566677#define MAXN 55LL fac[MAXN], res;int n, m, row[MAXN], col[MAXN], g[MAXN][2], hash[MAXN][MAXN] ;void init(){    fac[0] = 1;    for( int i = 1; i < MAXN; ++i )        fac[i] = ( fac[i-1] * i ) % MOD;}void dfs( int id, int num ){    if( id > m )    {        if( num & 1 )    res = ( ( res - fac[ n - num ] ) % MOD + MOD ) % MOD;        else             res = ( res + fac[ n - num ] ) % MOD;        return;    }    dfs( id + 1, num );    if( row[g[id][0]] == 0 && col[g[id][1]] == 0 )    {        row[g[id][0]] = col[g[id][1]] = 1;        dfs( id + 1, num + 1 );        row[g[id][0]] = col[g[id][1]] = 0;    } }int main(){    init();    while( ~scanf( "%d %d", &n, &m ) )    {        CLR( row, 0 ), CLR( col, 0 ), CLR( hash, 0 );        for( int i = 1; i <= m; ++i )        {            scanf( "%d %d", &g[i][0], &g[i][1] );            if( hash[g[i][0]][g[i][1]] )            {                --i;                --m;            }            else                hash[g[i][0]][g[i][1]] = 1;        }        res = 0;        dfs( 1, 0 );        res = ( res % MOD + MOD ) % MOD;        printf( "%lld\n", res );    }    return 0;}
学习的暴搜
#include <cstdio>#include <cstring>typedef long long LL;#define CLR( a, b ) memset( a, b, sizeof(a) )#define MAXN 55#define MOD 55566677LL fac[ MAXN ], C[ MAXN][ MAXN ], r[ MAXN ], R[ MAXN ], res;bool vis_r[ MAXN ], vis_c[ MAXN ], hash[ MAXN ][ MAXN ];int n, m, h[ MAXN ], v[ MAXN ], one, x, y;void init()    //递推初始化阶乘和组合数公式 {    fac[0] = 1;    for( int i = 1; i < MAXN; ++i )        fac[i] = ( fac[i-1] * i ) % MOD;        for( int i = 0; i < MAXN; ++i )        C[i][i] = C[i][0] = 1;    for( int i = 2; i < MAXN; ++i )    {        for( int j = 1; j < i; ++j )        {            C[i][j] = C[i - 1][j] + C[i - 1 ][j - 1];            if( C[i][j] >= MOD )    C[i][j] -= MOD;        }    }}void dfs( int k, int id ){    if( k > n )        return;    for( int i = id; i < n; ++i )    {        for( int j = 0; j < n; ++j )        {            if( !vis_r[i] && !vis_c[j] && hash[i][j] )            {                r[k]++;                if( r[k] >= MOD )    r[k] -= MOD;                                vis_r[i] = vis_c[j] = true;                dfs( k + 1, i );                vis_r[i] = vis_c[j] = false;            }        }    }} void cal(){    CLR( R, 0 );    R[0] = 1;    R[1] = m;    for( int i = 2; i <= n; ++i )    {        for( int j = 0; j <= one && j <= i; ++j )        {            R[i] += r[i - j] * C[one][j];            R[i] %= MOD;        }    }}LL solve(){    LL ans = fac[n];    LL k = -1;    for( int i = 1; i <= n; ++i )    {        ans += k * fac[n-i] * R[i];        k *= -1;    }    ans = ( ans % MOD + MOD ) % MOD;    return ans;}int main(){    init();    while( ~scanf( "%d %d", &n, &m ) )    {        CLR( h, 0 ); CLR( v, 0 );        CLR( r, 0 ); CLR( hash, false );        CLR( vis_r, false ); CLR( vis_c, false );        for( int i = 0; i < m; ++i )        {            scanf( "%d %d", &x, &y );            x--;            y--;            if( hash[x][y] )            {                i--;                m--;                continue;            }            h[x]++;            v[y]++;            hash[x][y] = 1;        }                one = 0;        for( int i = 0; i < n; ++i )        {            for( int j = 0; j < n; ++j )            {                if( hash[i][j] && ( h[i] <= 1 && v[j] <= 1 ) )                {                    hash[i][j] = false;                    one++;                }            }        }        r[0] = 1;        dfs( 1, 0 );        cal();        printf( "%lld\n", solve() );    }    return 0;}
禁位排列

 

ZOJ 3687 The Review Plan I ( 禁位排列 + 容斥原理 )