bzoj 2601: [Jsoi2011]同分异构体计数
标签：div 输出 script sig 帮助 连通 注意 一个 for
Description
Antonio 最近对有机化学比较感兴趣，他想请你帮助他快速计算出某种烃类的同分异
构体的数目。
为了表述方便，我们作出如下定义：
环烷烃： 具有n 个碳原子的环烷烃可以表示成一张具有n 个顶点n 条边的无向连通
简单图(基环+外向树)。每个顶点的度数不超过 4。
M-环烷烃：至多有m 个顶点在环上的环烷烃。（注意环上至少有 3 个顶点，因为
任意两个顶点之间至多只能有1 条边）。
同构：假设结构A和结构B 均具有n 个碳原子，A和B 同构当且仅当能够对A和
B 中的每个碳原子都按照 1~n 编号，使得对于编号为 v1 和 v2 的两个碳原子，他
们在 A中存在边相连当且仅当他们在 B中存在边相连。（换言之，A和 B对应的图
同构）。
现在，给出n, m，Antonio 希望你帮助他统计有多少种互不同构的含有n 个碳原子的
m-环烷烃。由于这个数量可能很大，你只需要输出它对p 的余数。（p是一个素数）。
在本题中，我们不考虑某结构在化学上是否能够稳定存在，也不考虑其他的异构方式。
Input
输入文件只有一行，用空格隔开的三个整数n, m, p 。保证有m
Output
输出文件有且仅有一行，表示具有n 个碳原子的互不同构的m-环烷烃的数量，对 p的
余数。
先处理出根的度为2，其余点度
环有旋转和翻转两种变换，由于m>=3，构成的置换群阶为2m，用burnside引理处理
旋转k(0
旋转+翻转需要分奇偶处理：
若m为奇数，则有m个这种置换，形成(m+1)/2个等价类，其中一个等价类包含1个位置，其余包含2个位置
若m为偶数
则有m/2个置换形成m/2个等价类，每个等价类包含2个位置
另有m/2个置换形成m/2+1个等价类，其中两个等价类包含1个位置，其余包含2个位置
#include
typedef unsigned long long u64;
typedef unsigned int u32;
int n,m;
u32 P;
int gcd(int a,int b){
for(int c;b;c=a,a=b,b=c%b);
return a;
}
int phi(int n){
int v=n;
for(int i=2;i*iif(n%i==0){
do n/=i;while(n%i==0);
v=v/i*(i-1);
}
if(n>1)v=v/n*(n-1);
return v;
}
inline u32 fix(int a){
return a+(a>>31&P);
}
struct num{
u32 x;
num(u32 a=0):x(a){}
num operator+(num w){return fix(x+w.x-P);}
num operator*(num w){return u64(x)*w.x%P;}
void operator+=(num w){x=fix(x+w.x-P);}
};
num s[5][1007],gs[11],iv[117],f0[57][1007],f1[57][1007],ans;
void cal(int m,int n){
int g=gcd(n,m);
num v=0;
for(int d=1;dif(g%d==0)v+=f0[m/d][n/d]*phi(d);
v+=f1[m][n]*m;
// printf("%d,%d:%d\n",m,n,v*iv[m*2]);
ans+=v*iv[m*2];
}
int main(){
scanf("%d%d%u",&n,&m,&P);
if(m>n)m=n;
s[0][0]=iv[1]=1;
for(int i=2;i115;++i)iv[i]=iv[P%i]*(P-P/i);
for(int i=1;ii){
f0[1][i]=f1[1][i]=s[0][i-1]+s[1][i-1]+s[2][i-1];
gs[1]=f0[1][i]+s[3][i-1];
// printf("[%d:%d]\n",i,gs[1]);
for(int j=2;j3;++j)gs[j]=gs[j-1]*(gs[1]+(j-1))*iv[j];
for(int j=3;j;--j){
for(int k=n;k>=i;--k){
for(int t=1;tt){
int w=k-t*i;
if(w>=0)s[j][k]+=gs[t]*s[j-t][w];
}
}
}
}
for(int i=2;ii){
for(int j=i;jj){
for(int k=1;k1][j-k]*f0[1][k];
if(i&1){
for(int k=2;k2)f1[i][j]+=f0[i>>1][k>>1]*f0[1][j-k];
}else{
for(int k=1;k1][j-k]*f0[1][k];
if(~j&1)f1[i][j]+=f0[i>>1][j>>1];
f1[i][j]=f1[i][j]*iv[2];
}
// printf("%d,%d %d %d\n",i,j,f0[i][j],f1[i][j]);
}
}
for(int i=3;ii)cal(i,n);
printf("%d\n",ans.x);
return 0;
}
bzoj 2601: [Jsoi2011]同分异构体计数
标签：div 输出 script sig 帮助 连通 注意 一个 for
原文地址：http://www.cnblogs.com/ccz181078/p/7147947.html
评论