BZOJ1488/HNOI2009/树的同构

Posted on By 二价氢

#题目描述

个点的无向图有几种?

#做法

搜索,见08年陈瑜希论文

#AC Code

打表

#include <iostream>
using namespace std;
int ans[]=
{
    1,
    1,
    2,
    4,
    11,
    34,
    156,
    47,
    382,
    493,
    291,
    56,
    400,
    993,
    778,
    96,
    890,
    888,
    766,
    749,
    7,
    304,
    785,
    887,
    46,
    799,
    403,
    68,
    742,
    852,
    567,
    582,
    803,
    231,
    122,
    61,
    761,
    151,
    931,
    617,
    870,
    170,
    736,
    521,
    412,
    976,
    217,
    383,
    119,
    447,
    314,
    793,
    952,
    321,
    665,
    663,
    780,
    791,
    78,
    403,
    683
};
int main()
{
    int n;
    cin>>n;
    cout<<ans[n]<<endl;
    return 0;
}

Q:为毛下面这个WA了,到n=46都是对的……

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,ans;
const int mod=997;
int h[65],a[65],f[5005];
int g[65][65];
int gcd(int x,int y)
{
	if (y==0)
		return x;
	else
		return gcd(y,x%y);
}
int Pow(int n,int k)
{
	int r=1;
	for (;k;k>>=1,(n*=n)%=mod)
		if (k&1)
			(r*=n)%=mod;
	return r;
}
void dfs(int dep,int n,int last,int t,int l,int k)
{
	int tt,kk;
	if (n==0)
		(ans+=t*f[k])%=mod;
	else
	{
		tt=t;kk=k;
		for (int i=last;i<=n;i++)
		{
			a[dep]=i;t=tt;k=kk;
			t=t*f[i>>1]*h[i]%mod;
			for (int j=1;j<=dep-1;j++)(k+=g[a[j]][i])%=mod;
			if (i==a[dep-1])l++;else l=1;
			(t*=h[l])%=mod;
			dfs(dep+1,n-i,i,t,l,k);
		}
	}
}
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			g[i][j]=gcd(i,j);
	f[0]=1;
	for (int i=1;i<=5000;i++)
		f[i]=(f[i-1]*2)%mod;
	for (int i=1;i<=n;i++)
		h[i]=Pow(i,mod-2);
	dfs(1,n,1,1,0,0);
	cout<<ans<<endl;
	return 0;
}