bzoj1488 [HNOI2009]圖的同構

http://www.elijahqi.win/archives/3429

Description

求兩兩互不同構的含n個點的簡單圖有多少種。

簡單圖是關聯一對頂點的無向邊不多于一條的不含自環的圖。

a圖與b圖被認為是同構的是指a圖的頂點經過一定的重新标号以後，a圖的頂點集和邊集能完全與b圖一一對應。

Input

輸入一行一個整數N，表示圖的頂點數，0<=N<=60

Output

輸出一行一個整數表示含N個點的圖在同構意義下互不同構的圖的數目，答案對997取模。

Sample Input

輸入1

1

輸入2

2

輸入3

3

Sample Output

輸出1

1

輸出2

2

輸出3

4

題目可以考慮等價為給每條邊染色 選那麼就是染1 反之就是染0那麼就是求這樣的方案數是多少

直接考慮邊的同構 并不可做 那麼我們不妨考慮通過點的置換來算邊的置換

觀察點置換可以發現結構相同的點置換->循環數相同的置換 即邊的循環數和點的循環數有關系

至于什麼關系後面認真觀察

通過觀察可以發現一條邊他的兩個點要麼在同一個點置換要麼在兩個點置換

那麼先考慮簡單的情況 在兩個點置換中 那麼我們通過多枚舉樣例可以感覺到假設我現在有兩個點置換

大小為l1,l2那麼他們構成的邊個數就是l1*l2 然而考慮他們兩個置換構成的邊的循環周期（長度）是lcm(l1,l2)

那麼循環個數就是l1*l2/(l1*l2/gcd(l1,l2))=gcd(l1,l2)

那麼考慮在一個置換裡的邊是什麼情況

點置換為偶數的時候有個特例即覆寫l/2的那個循環實際大小隻是1 是以我們最後加一即可

奇數的時候每個循環覆寫l條邊 總共c(l,2)條邊 這麼算一算即可

那麼歸結起來奇數和偶數點置換最後都會是l/2下取整這麼多的邊循環

直接暴力枚舉顯然複雜度不正确 但是 發現邊循環和點循環并不有直接關系 僅僅和循環大小有關系

是以我們不妨假設來枚舉一個數列l1<=l2<=l3…且l1+l2+l3+..=n這樣的話 再算出這樣的點置換有多少個一乘即可 複雜度大約∑i*log(i)

那麼考慮這樣一共有多少大小分别為l1,l2,l3這樣的循環的排列

最後的個數為 n!|l1|∗|l2|∗|l3|∗..∗s1!∗s2!∗s3! n ! | l 1 | ∗ | l 2 | ∗ | l 3 | ∗ . . ∗ s 1 ! ∗ s 2 ! ∗ s 3 ! 其中s1,s2分别為長度為1的置換出現的次數 長度為2的置換出現的次數 因為這樣做的話我們可以考慮全排列相比這些循環映射多了什麼 在一個循環映射裡1,2 2,1算一種 但是全排列卻算了兩次是以便有了多出的這些方案 于是我們直接除掉即可因為考慮如果是循環大小相同的也會因為互相的相對位置被多算是以也除掉即可

最後利用上面算出的東西結合polya即可得到答案

先枚舉點置換情況 算出邊置換的個數 應用polya 每個循環可以選擇填或者不填是以就算出方案然後 再 × × 這種情況下一共有多少個這樣的邊置換 最後在整體/邊置換總數即可

邊置換總數為n!

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
inline char gc(){
    static char now[<<],*S,*T;
    if (T==S){T=(S=now)+fread(now,,<<,stdin);if (T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=,f=;char ch=gc();
    while(!isdigit(ch)) {if (ch=='-') f=-;ch=gc();}
    while(isdigit(ch)) x=x*10+ch-'0',ch=gc();
    return x*f;
}
const int N=;const int mod=;
inline int gcd(int x,int y){return !y?x:gcd(y,x%y);}
inline int ksm(int b,int t){static int tmp;
    for (tmp=;t;b=b*b%mod,t>>=) if (t&) tmp=tmp*b%mod;return tmp;
}
int ans,n,v[N],jc[N],nm[N],cnt;
inline void dfs(int now,int left){
    if (left==){
        int tmp1=,tmp2=;
        for (int i=;i<=cnt;++i){
            tmp1+=nm[i]*(nm[i]-)*v[i]>>;tmp1+=v[i]/*nm[i];
            for (int j=i+;j<=cnt;++j) tmp1+=nm[i]*nm[j]*gcd(v[i],v[j]);
        }
        for (int i=;i<=cnt;++i)
            tmp2=tmp2*ksm(v[i],nm[i])*jc[nm[i]]%mod;
        tmp2=ksm(tmp2,mod-)*jc[n]%mod;ans=(ans+tmp2*ksm(,tmp1))%mod;
        return;
    }
    if(now>left) return;dfs(now+,left);
    for (int i=;i*now<=left;++i){
        v[++cnt]=now,nm[cnt]=i;dfs(now+,left-i*now);--cnt;
    }
}
int main(){
    freopen("bzoj1488.in","r",stdin);
    jc[]=;for (int i=;i<=;++i) jc[i]=jc[i-]*i%mod;
    n=read();dfs(,n);ans=ans*ksm(jc[n],mod-)%mod;printf("%d\n",ans);
    return ;
}