【BZOJ3162】独钓寒江雪（树哈希，动态规划）

题面

题解

忽然翻到这道题目，突然发现就是前几天一道考试题目。。。

题解：

树哈希，既然只考虑这一棵树，那么，如果两个点为根是同构的，

他们的重心相同，所以直接找出树的重心，以重心为根进行转移

提前预处理每一棵子树的哈希值，因为相同的子树是同构的，所以转移相当于是可重组合的计算。

对于存在两个重心的情况，分两个重心的子树同构还是不同构。

如果不同构则随便选择一个重心即可。如果同构，则建立一个虚点，然后\(dp\)

最后容斥一下即可。

中间算组合数的时候，发现只与儿子个数有关，所以可以爆算。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define ull unsigned long long

#define ll long long

#define RG register

#define MAX 500500

#define MOD 1000000007

#define inv2 500000004

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}

struct Line{int v,next;}e[MAX<<1];

int h[MAX],cnt=2;

inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}

int f[MAX][2],ans,n,size[MAX],rt,rt2,S[MAX],top,msz[MAX];

const ull base1=19;

const ull base2=19260817;

const ull base3=1e16+5;

ull Hash[MAX];

int jc[MAX],jv[MAX],inv[MAX];

bool cmp(int a,int b){return Hash[a]<Hash[b];}

int C(int n,int m)

{

	if(m<n-m)m=n-m;int ret=1;

	for(int i=n;i>m;--i)ret=1ll*ret*i%MOD;

	ret=1ll*ret*jv[n-m]%MOD;return ret;

}

void getroot(int u,int ff)

{

	size[u]=1;

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;if(v==ff)continue;

		getroot(v,u);size[u]+=size[v];

		msz[u]=max(msz[u],size[v]);

	}

	msz[u]=max(msz[u],n-size[u]);

	if(msz[u]<msz[rt])rt=u;

	else if(msz[u]==msz[rt])rt2=u;

}

void DFS(int u,int ff)

{

	for(int i=h[u];i;i=e[i].next)if(e[i].v!=ff)DFS(e[i].v,u);

	f[u][0]=f[u][1]=1;top=0;

	for(int i=h[u];i;i=e[i].next)if(e[i].v!=ff)S[++top]=e[i].v;

	sort(&S[1],&S[top+1],cmp);

	for(int i=1,j;i<=top;i=j+1)

	{

		j=i;while(j!=top&&Hash[S[j+1]]==Hash[S[i]])++j;

		int t=j-i+1,s0=(f[S[i]][0]+f[S[i]][1])%MOD,s1=f[S[i]][0];

		s0=C(s0+t-1,t);s1=C(s1+t-1,t);

		f[u][0]=1ll*f[u][0]*s0%MOD;f[u][1]=1ll*f[u][1]*s1%MOD;

	}

}

void GetHash(int u,int ff)

{

	Hash[u]=0;size[u]=1;int son=0;

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;if(v==ff)continue;

		GetHash(v,u);size[u]+=size[v];

		Hash[u]^=Hash[v]+base1;++son;

	}

	Hash[u]+=base2*size[u]+base3*son*son*size[u];

}

int main()

{

	n=read();jc[0]=jv[0]=inv[0]=inv[1]=1;msz[0]=1e9;

	for(int i=1;i<n;++i)

	{

		int u=read(),v=read();

		Add(u,v);Add(v,u);

	}

	for(int i=2;i<=n;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;

	for(int i=1;i<=n;++i)jc[i]=1ll*jc[i-1]*i%MOD;

	for(int i=1;i<=n;++i)jv[i]=1ll*jv[i-1]*inv[i]%MOD;

	getroot(1,0);

	if(msz[rt]==msz[rt2])

	{

		GetHash(rt,rt2);GetHash(rt2,rt);

		if(Hash[rt]!=Hash[rt2])

		{

			DFS(rt,rt2);DFS(rt2,rt);

			add(ans,1ll*f[rt][0]*f[rt2][0]%MOD);

			add(ans,1ll*f[rt][1]*f[rt2][0]%MOD);

			add(ans,1ll*f[rt][0]*f[rt2][1]%MOD);

		}

		else

		{

			Add(n+1,rt);Add(n+1,rt2);

			for(int i=h[rt2];i;i=e[i].next)if(e[i].v==rt){e[i].v=e[i^1].v=n+1;break;}

			DFS(n+1,0);ans=C(f[rt][1]+1,2);ans=MOD-ans;add(ans,f[n+1][0]);

		}

	}

	else GetHash(rt,0),DFS(rt,0),ans=(f[rt][0]+f[rt][1])%MOD;

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

	return 0;

}

巴特西

【BZOJ3162】独钓寒江雪（树哈希，动态规划）

【BZOJ3162】独钓寒江雪（树哈希，动态规划）

题面

题解

最新文章

热门文章