P4727 [HNOI2009]图的同构记数

传送门

如果我们把选出子图看成选出边，进而看成对边黑白染色，那么就是上一题的弱化版了，直接复制过来然后令\(m=2\)即可

不过直接交上去会T，于是加了几发大力优化

不知为何华丽的被小号抢了rank2

//minamoto

#include<bits/stdc++.h>

#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)

using namespace std;

const int N=105,P=997;

int ans,n,m,fac[N],inv[N],rec[N],Gcd[N][N];

int GCD(int i,int j){

    if(Gcd[i][j])return Gcd[i][j];

    if(!i)return Gcd[i][j]=j;if(!j)return Gcd[i][j]=i;

    return Gcd[i][j]=GCD(j,i%j);

}

int ksm(int x,int y){

    int res=1;

    for(;y;y>>=1,x=x*x%P)if(y&1)res=res*x%P;

    return res;

}

void calc(int x){

    int sum=0,mul=1,now=1;

    fp(i,1,x)sum+=rec[i]/2;

    fp(i,1,x)fp(j,i+1,x)sum+=Gcd[rec[i]][rec[j]];

    fp(i,1,x)(mul*=rec[i])%=P;

    fp(i,2,x){

        if(rec[i]!=rec[i-1])(mul*=fac[now])%=P,now=0;

        ++now;

    }(mul*=fac[now])%=P,mul=fac[n]*ksm(mul,P-2)%P;

    (ans+=mul*ksm(m,sum)%P)%=P;

}

void dfs(int k,int x,int s){

    if(!x)calc(k-1);if(x<s)return;

    fp(i,s,x)rec[k]=i,dfs(k+1,x-i,i);

}

void init(){

    fac[0]=1;fp(i,1,n)fac[i]=fac[i-1]*i%P;

    fp(i,1,n)Gcd[i][0]=Gcd[0][i]=i;

    fp(i,1,n)fp(j,1,n)GCD(i,j);

}

int main(){

//	freopen("testdata.in","r",stdin);

    scanf("%d",&n),m=2,init();

    dfs(1,n,1);(ans*=ksm(fac[n],P-2))%=P;

    printf("%d\n",ans);return 0;

}