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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

【置换群】[HNOI2008]Cards  

2014-04-20 17:48:12|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
第一次做置换群的题目……
一开始以为是什么奇怪的DP,一问才知道原来是群论
于是向zky学了Burnside引理+Polya定理
然后关于最后的取答案的方法wangxz神犇又交给俺两种做法(乘法逆元or欧拉定理)
感谢两位神犇!

/*
置换群 + Dp + 数论
*/
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
const int M = 100+1;
int n,m,rn,bn,gn,P;
int zh[M][2][M],xhj[M],ans,f[M][21][21][21];
short v[M];
int dfs(int i,int x){
v[x] = 1;
if(!v[zh[i][1][x]]) return dfs(i,zh[i][1][x])+1;
else return 1;
}
int dp(int nn,int n1,int n2,int n3){
if(n1==0&&n2==0&&n3==0&&nn==0) return 1;
if(n1<0||n2<0||n3<0||nn<=0) return 0;
int &re=f[nn][n1][n2][n3];
if(re!=-1) return re;
re=0;
re=(re+dp(nn-1,n1-xhj[nn],n2,n3))%P;
re=(re+dp(nn-1,n1,n2-xhj[nn],n3))%P;
re=(re+dp(nn-1,n1,n2,n3-xhj[nn]))%P;
return re;
}
typedef long long LL;
//ax+by=d=gcd(a,b)
int exgcd(int a,int b,LL &d,LL &x,LL &y){
if(!b){d=a;x=1;y=0;}
else{exgcd(b,a%b,d,y,x);y-=x*(a/b);}
}
//乘法逆元
int inv(int a,int n){
LL d,x,y;
exgcd(a,n,d,x,y);
return d==1?(x+n)%n:-1;
}
//读入优化
int scan(){
char cc=' ';int re=0,fs=0;
while((cc==' '||cc=='\n')&&cc!=EOF) cc=getchar();
if(cc=='-'){fs=1;cc=getchar();}
if(cc=='+'){fs=0;cc=getchar();}
while((cc=='0')&&cc!=EOF) cc=getchar();
while('0'<=cc&&cc<='9'){
re=re*10+(cc-'0');
cc=getchar();
}
return re*(fs?-1:1);
}
int main(){
int i,j,a,b,c;
rn=scan();bn=scan();gn=scan();
m=scan();P=scan();
n = rn+bn+gn;
for(i=1;i<=m;i++){
for(j=1;j<=n;j++){
zh[i][0][j]=j;
zh[i][1][j]=scan();
}
}
for(i=1;i<=n;i++)
zh[m+1][0][i]=zh[m+1][1][i]=i;
//每个置换方式
for(i=1;i<=m+1;i++){
memset(xhj,0,sizeof(xhj));
memset(v,0,sizeof(v));
memset(f,-1,sizeof(f));
for(j=1;j<=n;j++)
if(!v[j]){
xhj[++xhj[0]] = dfs(i,j);
}
//dp
ans=((long long)ans + dp(xhj[0],rn,bn,gn))%P;
}
//乘法逆元
int ny = inv(m+1,P);
printf("%d\n",(ans*ny)%P);
return 0;
}


记忆化搜索因为各种奇葩的问题写挂了……
【置换群】[HNOI2008]Cards - 时光机 - 时光机TimeMachine
 第一个RE是因为没有去掉文件,不要在意……
  评论这张
 
阅读(14)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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