bzoj1004[HNOI2008] Cards

本文主要是介绍bzoj1004[HNOI2008] Cards，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：bzoj1004
题目大意：
有3种颜色:红色,蓝色,绿色。要求染出Sr张红色,Sb张蓝色,Sg张绿色。M种不同的洗牌法,这里问有多少种不同的染色方案。两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可以使用多次)洗成另一种。要求出答案除以P的余数(P为质数)。100%数据满足 Max{Sr,Sb,Sg}≤20；m≤60,m+1<p<100
输入数据保证任意多次洗牌都可用这 m种洗牌法中的一种代替，且对每种洗牌法，都存在一种洗牌法使得能回到原状态。

题解：
置换+dp

对于每个置换就暴力找循环节。然后f[i][j][k]分别表示用了i张红色,j张蓝色,k张绿色的方案，dp一下就好了。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 70bool vis[N];int sa,sb,sc,num;
int mod,a[N],g[N],f[N][N][N];
void dp()
{memset(f,0,sizeof(f));int p,i,j,k;f[0][0][0]=1;for (p=1;p<=num;p++)for (i=sa;i>=0;i--)for (j=sb;j>=0;j--)for (k=sc;k>=0;k--){if (i>=g[p]) f[i][j][k]=(f[i][j][k]+f[i-g[p]][j][k])%mod;if (j>=g[p]) f[i][j][k]=(f[i][j][k]+f[i][j-g[p]][k])%mod;if (k>=g[p]) f[i][j][k]=(f[i][j][k]+f[i][j][k-g[p]])%mod;}
}
int qpow(int x,int tt)
{int ret=1;while (tt){if (tt&1) ret=(ret*x)%mod;x=(x*x)%mod;tt>>=1;}return ret;
}
int main()
{freopen("a.in","r",stdin);freopen("a.out","w",stdout);int m,n,ans,i,j;scanf("%d%d%d%d%d",&sa,&sb,&sc,&m,&mod);n=sa+sb+sc;ans=0;m++;for (i=1;i<=m;i++){num=0;if (i<m) for (j=1;j<=n;j++) {scanf("%d",&a[j]);vis[j]=true;}else for (j=1;j<=n;j++) a[j]=j,vis[j]=true;for (j=1;j<=n;j++) if (vis[j]){int x=j,cnt=0;while (vis[x]){vis[x]=false;cnt++;x=a[x];}g[++num]=cnt;}dp();ans=(ans+f[sa][sb][sc])%mod;}ans=(qpow(m,mod-2)*ans)%mod;//G是置换群 所以|G|是指置换的个数 所以是m而不是元素n的个数printf("%d\n",ans);return 0;
}

天天吞我题解好气啊

这篇关于bzoj1004[HNOI2008] Cards的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---