首页 > 代码库 > 组合计数(polya计数):SGU 282 Isomorphism
组合计数(polya计数):SGU 282 Isomorphism
因为论文的题解写得太好了,直接贴。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 typedef long long LL; 6 const int N=55;int st[N]; 7 LL n,m,Mod,fac[N],ifac[N],pow[N],ans; 8 LL Inv(LL x){return x==1?x:(Mod-Mod/x)*Inv(Mod%x)%Mod;} 9 LL Gcd(LL a,LL b){return b?Gcd(b,a%b):a;} 10 void DFS(int d,int c,int l){ 11 if(c==0){ 12 LL tot=1;int t=0; 13 for(int i=1;i<=d;i++) 14 tot=tot*Inv(st[i])%Mod; 15 for(int i=1;i<=d;i++) 16 if(st[i]!=st[i-1]){ 17 tot=tot*ifac[t]%Mod; 18 t=1; 19 } 20 else t+=1; 21 tot=tot*ifac[t]%Mod; 22 for(int i=1;i<=d;i++) 23 tot=tot*pow[st[i]/2]%Mod; 24 for(int i=1;i<=d;i++) 25 for(int j=i+1;j<=d;j++) 26 tot=tot*pow[Gcd(st[i],st[j])]%Mod; 27 ans=(ans+tot)%Mod; 28 } 29 for(int i=l;i<=c;i++) 30 st[d+1]=i,DFS(d+1,c-i,i); 31 } 32 int main(){ 33 scanf("%I64d%I64d%I64d",&n,&m,&Mod); 34 pow[0]=fac[0]=ifac[0]=1; 35 for(int i=1;i<=n;i++){ 36 fac[i]=1ll*fac[i-1]*i%Mod; 37 pow[i]=pow[i-1]*m%Mod; 38 ifac[i]=Inv(fac[i]); 39 } 40 DFS(0,n,1);printf("%I64d\n",ans); 41 return 0; 42 }
组合计数(polya计数):SGU 282 Isomorphism
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。