首页 > 代码库 > 【bzoj1004】 HNOI2008—Cards
【bzoj1004】 HNOI2008—Cards
http://www.lydsy.com/JudgeOnline/problem.php?id=1004 (题目链接)
题意
n张卡片,染成3种颜色,每种颜色只能染固定张数。给出一些洗牌方案,问染色方案数。
Solution
Burnside引理。
左转题解:LCF
代码
// bzoj1004#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 1<<30#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=100;LL f[maxn][maxn][maxn],a[maxn],vis[maxn],size[maxn];LL n,m,P,R,G,B;LL power(LL a,LL b) { LL res=1; while (b) { if (b&1) res=res*a%P; a=a*a%P;b>>=1; } return res;}LL dp() { memset(vis,0,sizeof(vis)); memset(f,0,sizeof(f)); int cnt=0; for (int i=1;i<=n;i++) if (!vis[i]) { size[++cnt]=0; for (int j=a[i];!vis[j];j=a[j]) vis[j]=1,size[cnt]++; } f[0][0][0]=1; for (int i=1;i<=cnt;i++) for (int r=R;r>=0;r--) for (int b=B;b>=0;b--) for (int g=G;g>=0;g--) { if (r>=size[i]) f[r][b][g]=(f[r][b][g]+f[r-size[i]][b][g])%P; if (b>=size[i]) f[r][b][g]=(f[r][b][g]+f[r][b-size[i]][g])%P; if (g>=size[i]) f[r][b][g]=(f[r][b][g]+f[r][b][g-size[i]])%P; } return f[R][B][G]%P;}int main() { scanf("%lld%lld%lld%lld%lld",&R,&B,&G,&m,&P); n=R+B+G;LL ans=0; for (int i=1;i<=n;i++) a[i]=i; ans=(ans+dp())%P; for (int i=1;i<=m;i++) { for (int j=1;j<=n;j++) scanf("%lld",&a[j]); ans=(ans+dp())%P; } ans*=power(m+1,P-2); printf("%lld",ans%P); return 0;}
【bzoj1004】 HNOI2008—Cards
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。