首页 > 代码库 > 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 ( 禁位排列 + 容斥原理 )
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。