【BZOJ1004】【HNOI20008】cards

看黄学长的代码才写出来的,sro_hzwer_orz

原题:

小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有
多少种染色方案,Sun很快就给出了答案.进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绝色.他又询问有多少种方
案,Sun想了一下,又给出了正确答案. 最后小春发明了M种不同的洗牌法,这里他又问Sun有多少种不同的染色方案.
两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可以使用多次)洗
成另一种.Sun发现这个问题有点难度,决定交给你,答案可能很大,只要求出答案除以P的余数(P为质数).

m<=60,m+1<p<100,Max{Sr,Sb,Sg}<=20。

已经把置换给出来了,要么burnside,要么polya,然而这题颜色有使用限制,所以不能用polya(polya还没理解,这里还不懂)

所以就用burnside:一个置换群的等价计数=(每个置换的置换后等价情况数)/置换总数

置换后的等价情况数就是在置换中没变的数,这个很好写

然后在置换中没变的数要刷的颜色是一样的,只有三种颜色所以就可以搞个三维的01包计数

最后除的内个置换总数因为要膜,所以要用到除法逆元

怎么用呐:

bx mod p=1,x就是b模P的乘法逆元,呢么x≡1/b(mod p),呢么a/b≡ax(mod p),然后用扩展欧几里得求乘法逆元即可(就是解bx mod p=1,某年NOIPT1)

代码:

 #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int sr,sb,sg,n,m,p;
int huan[][];
bool visited[];
int ge[];
int f[][][];
int ans=;
void exgcd(int a,int b,int &x,int &y){
if(!b){ x=,y=; return ;}
exgcd(b,a%b,x,y);
int t=x; x=y; y=t-a/b*y;
}
int dp(int x){
memset(visited,,sizeof(visited));
int cnt=,temp;
for(int i=;i<=n;i++)if(!visited[i]){
visited[i]=true;
ge[++cnt]=; temp=i;
while(!visited[huan[x][temp]]){
ge[cnt]++;
visited[huan[x][temp]]=true;//这里容易蒙……
temp=huan[x][temp];//temp指向了这个连的下一个,再次循环时判断的是下一个的下一个……
}
}
memset(f,,sizeof(f)); f[][][]=;
for(int t=;t<=cnt;t++)
for(int i=sr;i>=;i--)
for(int j=sb;j>=;j--)
for(int k=sg;k>=;k--){
if(i>=ge[t]) f[i][j][k]=(f[i][j][k]+f[i-ge[t]][j][k])%p;
if(j>=ge[t]) f[i][j][k]=(f[i][j][k]+f[i][j-ge[t]][k])%p;
if(k>=ge[t]) f[i][j][k]=(f[i][j][k]+f[i][j][k-ge[t]])%p;
}
return f[sr][sb][sg];
}
int main(){//freopen("ddd.in","r",stdin);
cin>>sr>>sb>>sg>>m>>p;
n=sr+sb+sg;
for(int i=;i<=m;i++)
for(int j=;j<=n;j++)
scanf("%d",&huan[i][j]);
m++;
for(int i=;i<=n;i++) huan[m][i]=i;//注意还有不置换的情况
for(int i=;i<=m;i++)
ans=(ans+dp(i))%p;
int x,y;
exgcd(m,p,x,y);
while(x<=)x+=p;
cout<<ans*x%p<<endl;
return ;
}
上一篇:Linux系统磁盘管理(lvm逻辑卷管理)


下一篇:学习练习 java编写西游记人物类