BZOJ1004: [HNOI2008]Cards
2024-08-27 05:45:15
三维01背包算出在每一个置换下不变的染色方案数,Burnside引理计算答案。
PS:数据太水所以只算恒等置换也是可以过的。
#include<bits/stdc++.h>
using namespace std;
int n,m,p,x,y,z;
bool u[61];
int f[21][21][21],s[61],v[61];
int power(int u,int v){
int d=1;
for(;v;v>>=1){
if(v&1)
d=d*u%p;
u=u*u%p;
}
return d;
}
void add(int& u,int v){
u=(u+v)%p;
}
int main(){
scanf("%d%d%d%d%d",&x,&y,&z,&m,&p);
n=x+y+z;
int ans=1;
for(int i=1;i<=n;++i)
ans=ans*i%p;
for(int i=1;i<=x;++i)
ans=ans*power(i,p-2)%p;
for(int i=1;i<=y;++i)
ans=ans*power(i,p-2)%p;
for(int i=1;i<=z;++i)
ans=ans*power(i,p-2)%p;
for(int t=0;t!=m;++t){
for(int i=1;i<=n;++i)
scanf("%d",s+i);
memset(u,0,sizeof u);
int cnt=0;
for(int i=1;i<=n;++i)
if(!u[i]){
int k=u[i]=1;
for(int j=s[i];j!=i;j=s[j])
k+=u[j]=1;
v[cnt++]=k;
}
memset(f,0,sizeof f);
f[0][0][0]=1;
for(int a=0;a!=cnt;++a)
for(int i=x;~i;--i)
for(int j=y;~j;--j)
for(int k=z;~k;--k){
if(i>=v[a])
add(f[i][j][k],f[i-v[a]][j][k]);
if(j>=v[a])
add(f[i][j][k],f[i][j-v[a]][k]);
if(k>=v[a])
add(f[i][j][k],f[i][j][k-v[a]]);
}
add(ans,f[x][y][z]);
}
printf("%d\n",ans*power(m+1,p-2)%p);
}
最新文章
- yaf框架学习笔记
- 说说设计模式~桥梁模式(Bridge)
- 《机器学习实战》学习笔记——第2章 KNN
- javascript 拷贝文本
- UVA 1291 十四 Dance Dance Revolution
- android Material Design:主题
- jquery 显示“加载状态 结束”
- Java的finally理解
- JMeter录制脚本
- ASP.NET三层架构的分析
- 开源 java CMS - FreeCMS2.3 留言管理
- iOS之 Auto Layout
- bzoj1934
- 前端技术之_CSS详解第一天
- elementui+vuejs如何添加表格操作按钮
- [CSS] input样式定制
- python爬虫套件在mac上的安装-bs的安装
- sublime快捷键的使用
- Linux内核分析第六周总结
- 转 Java笔记:Java内存模型