bzoj 1004: [HNOI2008]Cards

/**************************************************************Problem: 1004User: lxy8584099Language: C++Result: AcceptedTime:264 msMemory:1896 kb ****************************************************************//*刚好在学polya 就送来一个例题。。。首先 那b啥定理的优化版polya不起作用因为规定了某一种颜色的数量所以使用dp背包计数  f(r,b,g) 表示 用r个红 b个蓝 g个绿 的方案数（我们用不了优化 只能把所有方案数算出来。。）注意 单位元（也就是不置换）也算一种置换 要算进去还有 背包技术和01背包类似。 是倒着for 不然就要记录重复。。。 */ #include<cstdio> #include<cstring> using namespace std; const int N=65; int sr,sb,sg,n,m,p,cnt,ans; int a[N],size[N],f[N][N][N]; bool vis[N]; int ksm(int a,int b,int p) {int res=1;for(;b;b>>=1){if(b&1) (res*=a)%=p; (a*=a)%=p;} return res; } int getans() {memset(vis,0,sizeof(vis));memset(f,0,sizeof(f));memset(size,0,sizeof(size));f[0][0][0]=1;cnt=0;for(int i=1;i<=n;i++) if(!vis[i]){cnt++;  int x=i;while(!vis[x]) {size[cnt]++;vis[x]=1;x=a[x];} }for(int i=1;i<=cnt;i++)for(int r=sr;r>=0;r--)for(int b=sb;b>=0;b--)for(int g=sg;g>=0;g--){if(r>=size[i]) (f[r][b][g]+=f[r-size[i]][b][g])%=p;if(b>=size[i]) (f[r][b][g]+=f[r][b-size[i]][g])%=p;if(g>=size[i]) (f[r][b][g]+=f[r][b][g-size[i]])%=p;}return f[sr][sb][sg]; } int main() {scanf("%d%d%d%d%d",&sr,&sb,&sg,&m,&p);n=sr+sb+sg;for(int k=1;k<=m;k++){for(int i=1;i<=n;i++) scanf("%d",&a[i]);(ans+=getans())%=p;   // 计算每组置换的贡献     }for(int i=1;i<=n;i++) a[i]=i;(ans+=getans())%=p;     // 单位元的计算  (ans*=ksm(m+1,p-2,p))%=p;printf("%d\n",ans%p);return 0; }

 

转载于:https://www.cnblogs.com/lxy8584099/p/10139786.html

总结

以上是生活随笔为你收集整理的bzoj 1004: [HNOI2008]Cards的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。