BZOJ 1004: [HNOI2008]Cards [Polya 生成函数DP]

传送门

题意:三种颜色,规定使用每种颜色次数$r,g,b$,给出一个置换群,求多少种不等价着色

$m \le 60,\ r,g,b \le 20$


咦,规定次数?

《组合数学》上不是有生成函数做法吗....

生成函数貌似可以和背包$DP$互相转换来着

然后就做出来了

每种置换求循环,$d[i][j][k][l]$表示前$i$个循环有了$j$个红$k$个绿$l$个蓝

遇到一点小问题,一直输出$0$

看了黄学长的代码发现他加了一个恒等置换....

想了一会儿才明白题目给的不是置换群,因为少了一个恒等置换.....

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return x*f;
} int n,r,b,g,m,P,a[N];
int f[N],d[N][][],w[N],ans;
bool vis[N];
inline void mod(int &x){if(x>=P) x-=P;}
void dp(){
int s=;
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++) if(!vis[i]){
int u=a[i],len=;
while(u!=i) vis[u]=,len++,u=a[u];
w[++s]=len;
}
memset(d,,sizeof(d));
d[][][]=;
for(int i=;i<=s;i++)
for(int j=r;j>=;j--)
for(int k=g;k>=;k--)
for(int l=b;l>=;l--){
if(j>=w[i]) mod(d[j][k][l]+=d[j-w[i]][k][l]);
if(k>=w[i]) mod(d[j][k][l]+=d[j][k-w[i]][l]);
if(l>=w[i]) mod(d[j][k][l]+=d[j][k][l-w[i]]);
}
mod(ans+=d[r][g][b]);
}
inline int Pow(int a,int b){
int re=;
for(;b;b>>=,a=a*a%P)
if(b&) re=re*a%P;
return re;
}
inline int Inv(int a){return Pow(a,P-);}
int main(){
freopen("in","r",stdin);
r=read();b=read();g=read();m=read();P=read();
n=r+b+g;
for(int j=;j<=m;j++){
for(int i=;i<=n;i++) a[i]=read();
dp();
}
m++;
for(int i=;i<=n;i++) a[i]=i;
dp();
ans=ans*Inv(m)%P;
printf("%d",ans);
}
上一篇:[bzoj1004][HNOI2008][Cards] (置换群+Burnside引理+动态规划)


下一篇:js LINQ教程