bzoj 1004 Cards 组合计数

这道题考察的是组合计数（用Burnside，当然也可以认为是Polya的变形，毕竟Polya是Burnside推导出来的）。

这一类问题的本质是计算置换群(A,P)中不动点个数！（所谓不动点，是一个二元组(a,p)，a∈A，p∈P ，使得p(a)=a，即a在置换p的作用后还是a）。

Polya定理其实就是告诉了我们一类问题的不动点数的计算方法。

对于Burnside定理的考察，我见过的有以下几种形式（但归根结底还是计算不动点数）：

　　1、限制a(a∈A)的特点，本题即是如此（限制了各颜色个数，可以用DP来统计（以前我们直接用c^k来计算某置换的不动点，c是颜色总数，k是循环节个数））

　　2、让P的数量高出暴力的范围，（比如经典的项链染色问题，或者P就是一个对称群（包含所有置换）），此时就必须寻找数学规律，不能硬来。项链染色这种可以用欧拉函数优化；对于图的同构计数（它的置换群是一个对称群），先将置换按照其格式分类（见《组合数学》，可以想象具有相同格式的置换的不动点也是相同的），然后再观察某一特定格式的置换的不动点数是多少（是有规律的）。

注：应用定理解题时要保证置换成群，本题中，结合律是肯定的，输入说明中已经说了，该置换集合满足：封闭性，逆元，所以我们自己再添一个单位元（(1)(2)...(m))就行了。

 /**************************************************************

     Problem: 1004

     User: idy002

     Language: C++

     Result: Accepted

     Time:116 ms

     Memory:844 kb

 ****************************************************************/

 #include <cstdio>

 #include <cstring>

 #define maxn 65

 using namespace std;

 int mpow( int a, int b, int n ) {

     a %= n;

     int rt;

     for( rt=; b; b>>=,a=(a*a)%n )

         if( b& ) rt=(rt*a)%n;

     return rt;

 }

 int inv( int a, int n ) {

     return mpow(a,n-,n);

 }

 int sp[maxn], tot;

 bool vis[maxn];

 void split( int n, int *a ) {

     tot = ;

     memset( vis, , sizeof(vis) );

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

         if( vis[i] ) continue;

         tot++;

         sp[tot] = ;

         int cur = i;

         do {

             sp[tot]++;

             vis[cur] = true;

             cur = a[cur];

         } while( !vis[cur] );

     }

 }

 int n, sr, sg, sb, m, p, ans;

 int a[maxn];

 int dp[][][];

 int dodp() {

     memset( dp, , sizeof(dp) );

     dp[][][] = ;

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

         int sz = sp[i];

         for( int r=sr; r>=; r-- )

             for( int g=sg; g>=; g-- )

                 for( int b=sb; b>=; b-- ) {

                     int & dv = dp[r][g][b];

                     dv = ;

                     if( r>=sz ) dv += dp[r-sz][g][b];

                     if( g>=sz ) dv += dp[r][g-sz][b];

                     if( b>=sz ) dv += dp[r][g][b-sz];

                     dv %= p;

                 }

     }

     return dp[sr][sg][sb];

 }

 void update( int n, int *a ) {

     split(n,a);

     ans += dodp();

     if( ans>p ) ans -= p;

 }

 int main() {

     scanf( "%d%d%d%d%d", &sr, &sg, &sb, &m, &p );

     n = sr+sg+sb;

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

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

             scanf( "%d", a+j );

         update(n,a);

     }

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

         a[i] = i;

     update(n,a);

     ans *= inv(m+,p);

     ans %= p;

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

 }

秒客网

bzoj 1004 Cards 组合计数

相关文章