注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-1004: [HNOI2008]Cards (Burnside定理+背包)  

2014-04-24 17:19:00|  分类: burnside定理,背 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1004


GDOI将即我个傻叉才跑去学了等价类计数,学了之后才发现这道我拖了N年的题原来只是入门题额。。。

根据Burnside定理,不同的等价类等于所有置换(记得把自身这个置换加进去)不动点的均值,那么就用个背包来求总数,然后乘法逆元一下求均值就可以了。(其实我觉得这里乘法逆元是有可能挂的,不过数据不强就不要在意了额。。。)。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

  • const int maxn =21;

  •  

  • int sr , sb , sg , m , mod , f[ maxn ][ maxn ][ maxn ], a[ maxn *3], n ;

  • bool used[ maxn *3];

  • int v[ maxn *3], cnt , ans =0;

  •  

  • void update(int&num ,int val ){

  •     ( num += val )%= mod ;

  • }

  •  

  • int power(int val ,int times ){

  •     int rec =1;

  •     for(; times ; times >>=1){

  •         if( times &1)( rec *= val )%= mod ;

  •         ( val *= val )%= mod ;

  •     }

  •     return rec ;

  • }

  •  

  • int main(  ){

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

  •     n = sr + sb + sg ;

  •     for(int w =0; w ++< m +1;){

  •         if( w < m +1)for(int i =0; i ++< n ;)scanf("%d", a + i );

  •         else for(int i =0; i ++< n ;) a[ i ]= i ;

  •         memset( used ,false,sizeof( used ));

  •         cnt =0;

  •         for(int i =0; i ++< n ;)if(! used[ i ]){

  •             v[++ cnt ]=0;

  •             for(int j = i ;! used[ j ]; j = a[ j ]){

  •                 ++ v[ cnt ], used[ j ]=true;

  •             }

  •         }

  •         memset( f ,0,sizeof( f ));

  •         f[0][0][0]=1;

  •         for(int h =0; h ++< cnt ;){

  •             for(int i = sr ; i >=0;-- i ){

  •                 for(int j = sb ; j >=0;-- j ){

  •                     for(int k = sg ; k >=0;-- k ){

  •                         if( i >= v[ h ])update( f[ i ][ j ][ k ], f[ i - v[ h ]][ j ][ k ]);

  •                         if( j >= v[ h ])update( f[ i ][ j ][ k ], f[ i ][ j - v[ h ]][ k ]);

  •                         if( k >= v[ h ])update( f[ i ][ j ][ k ], f[ i ][ j ][ k - v[ h ]]);

  •                     }

  •                 }

  •             }

  •         }

  •         update( ans , f[ sr ][ sb ][ sg ]);

  •     }

  •     ( ans *=power( m +1, mod -2))%= mod ;

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

  •     return 0;

  • }



  评论这张
 
阅读(2)| 评论(5)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017