洛谷4895 独钓寒江雪 （树哈希+dp+组合）
2024-09-07 22:27:18
qwq
首先，如果是没有要求本质不同的话，那么还是比较简单的一个树形dp
我们令\(dp[i][0/1]\)表示是否\(i\)的子树，是否选\(i\)这个点的方案数。
一个比较显然的想法。
\(dp[i][0]=\prod (dp[p][0]+dp[p][1])\)
\(dp[i][1]=\prod dp[p][0]\)
最后直接将一号点的答案加起来就好。
qwq但是如果写一发，就会发现第二个样例就wei掉了
（因为题目要求本质不同）
qwq
那么这个东西应该怎么做呢。
因为本质不同，所以对于\(x\)形态和\(y\)形态，在同一个根的两个形态一样的子树中，顺序并不影响贡献的。
所以考虑如果存在相同的应该怎么计算答案。
为了避免出现子树和整棵树除去这个子树之后的形态相似。
我们选择用重心来当做整个树的根。
因为重心的每个儿子都小于\(\frac{size}{2}\)
（如果存在两个重心的话，一个比较简便的计算方法就是用一个新点，连接两个点）
那么由于题目中的本质不同是旋转同构，所以如果两个子树形态相同，但是处于不同的子树，不需要一起计算（因为没法保证其他部分还相同）
所以我们就要求的是，对于每一个子树，求他本质相同的子树的贡献。
那么同一个形态的子树应该怎么统计答案呢。
int p = (dp[v[i-1]][0]+dp[v[i-1]][1])%mod;
int pp = dp[v[i-1]][0]%mod;
p%=mod;
pp%=mod;
//dp[x][0]=(dp[x][0]*C(p+now-1,p-1))%mod;
//dp[x][1]=(dp[x][1]*C(pp+now-1,pp-1))%mod;
dp[x][0]=(dp[x][0]*C(p+now-1,now))%mod;
dp[x][1]=(dp[x][1]*C(pp+now-1,now))%mod;//隔板，允许为空
//由于要求本质不同，所以我们相当于对于这now个同形态子树，放到对应的方案数的箱子里，允许为空，所以是隔板法、
//因为AAB和BAA是本质相同的。
now=1;
因为AAB和BAA是本质相同的。
所以其实我们将相当于把一些方案数，放到不同的子树内部。因为影响的答案只会是每个形态的个数。
这个是一个组合数，如果方案数是\(p\)，然后同形态的子树个数是\(now\)，
\[C^{now}_{p+now-1}
\]
\]
实际上这个是隔板（允许为空），一个经典套路
但是为了计算方便，我们选择选与他对称的一个组合数进行计算，因为\(now\)的范围是\(O(n)\)的，我们可以直接用循环求组合数（其实也没别的办法啊）
那么现在就剩下一个问题了，就是如何判断形态相同。
这时候就需要树哈希了
sro DT_Kang orz
这里用的是亢爷的一种树哈希的做法。
void dfs1(int x,int fa)
{
int num=0;
vector<int> v;
v.clear();
ha[x]=1;
for (int i=point[x];i;i=nxt[i])
{
int p = to[i];
if (p==fa) continue;
dfs1(p,x);
}
for (int i=point[x];i;i=nxt[i])
{
int p = to[i];
if (p==fa) continue;
v.pb(p);
num++;
}
sort(v.begin(),v.end(),cmp);
for (int i=0;i<num;i++)
{
ha[x]=(ha[x]+ha[v[i]]*mi[i+1])%mod;
}
ha[x]=ha[x]*size[x]%mod;
}
首先，我们对于每个子树，统计他的每个儿子，按照哈希值进行排序，从小到大乘上\(mi\)，然后最后用整个的哈希值，乘上子树大小
（可以直接当成一个套路去记）
下面弄上整个代码。
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define int long long
#define pb push_back
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
const int maxn = 1e6+1e2;
const int maxm = 2*maxn;
const int mod = 1e9+7;
const int qwq = 2333;
int point[maxn],nxt[maxm],to[maxm];
int cnt=1,n,m;
int ha[maxn];
int size[maxn],root,root1,root2;
int dp[maxn][2];
int mx[maxn];
int mi[maxn];
int power[maxn],inv[maxn];
int maxson,ymh=1e9;
void addedge(int x,int y)
{
nxt[++cnt]=point[x];
to[cnt]=y;
point[x]=cnt;
}
int qsm(int i,int j)
{
int ans=1;
while (j)
{
if (j&1) ans=ans*i%mod;
j>>=1;
i=i*i%mod;
}
return ans;
}
int C(int n,int m)
{
n=n%mod;
m=(m+mod)%mod;
int ans=1;
for (int i=n-m+1;i<=n;i++) ans=ans*i%mod;
//if (inv[m]==0) cout<<m<<"()()("<<endl;
ans=ans*inv[m]%mod;
//int ss=ans+1;
return ans;
}
void init(int n)
{
n+=10;
power[0]=1;
inv[0]=1;
for (int i=1;i<=n;i++) power[i]=power[i-1]*i%mod;
inv[n]=qsm(power[n],mod-2);
for (int i=n-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
mi[0]=1;
for (int i=1;i<=n;i++) mi[i]=mi[i-1]*qwq%mod;
}
void getroot(int x,int fa)
{
size[x]=1;
for (int i=point[x];i;i=nxt[i])
{
int p = to[i];
if (p==fa) continue;
getroot(p,x);
size[x]+=size[p];
mx[x]=max(mx[x],size[p]);
}
mx[x]=max(mx[x],n-size[x]);
if (mx[x]<ymh)
{
ymh=mx[x];
root1=x;
}
else if (mx[x]==ymh) root2=root1,root1=x;
}
void dfs(int x,int fa)
{
size[x]=1;
for (int i=point[x];i;i=nxt[i])
{
int p = to[i];
if (p==fa) continue;
dfs(p,x);
size[x]+=size[p];
}
}
int a[maxn];
bool cmp(int a,int b) //sro DT_Kang orz
{
return ha[a]<ha[b];
}
void dfs1(int x,int fa)
{
int num=0;
vector<int> v;
v.clear();
ha[x]=1;
for (int i=point[x];i;i=nxt[i])
{
int p = to[i];
if (p==fa) continue;
dfs1(p,x);
}
for (int i=point[x];i;i=nxt[i])
{
int p = to[i];
if (p==fa) continue;
v.pb(p);
num++;
}
sort(v.begin(),v.end(),cmp);
for (int i=0;i<num;i++)
{
ha[x]=(ha[x]+ha[v[i]]*mi[i+1])%mod;
}
ha[x]=ha[x]*size[x]%mod;
}
void solve(int x,int fa)
{
dp[x][0]=dp[x][1]=1;
int num=0;
vector<int> v;
v.clear();
for (int i=point[x];i;i=nxt[i])
{
int p = to[i];
if (p==fa) continue;
solve(p,x);
v.pb(p);
num++;
}
sort(v.begin(),v.end(),cmp);
int now = 1;
v.pb(n+2);
for (int i=1;i<=num;i++)
{
//cout<<v[i]<<"***"<<" ";
if (ha[v[i]]!=ha[v[i-1]])
{
int p = (dp[v[i-1]][0]+dp[v[i-1]][1])%mod;
int pp = dp[v[i-1]][0]%mod;
p%=mod;
pp%=mod;
//dp[x][0]=(dp[x][0]*C(p+now-1,p-1))%mod;
//dp[x][1]=(dp[x][1]*C(pp+now-1,pp-1))%mod;
dp[x][0]=(dp[x][0]*C(p+now-1,now))%mod;
dp[x][1]=(dp[x][1]*C(pp+now-1,now))%mod;//隔板，允许为空
//由于要求本质不同，所以我们相当于对于这now个同形态子树，放到对应的方案数的箱子里，允许为空，所以是隔板法、
//因为AAB和BAA是本质相同的。
now=1;
}
else
now++;
//cout<<v[i]<<endl;
}
//if (dp[x][0]==0) cout<<x<<" "<<dp[x][0]<<endl;
}
signed main()
{
n=read();ha[n+2]=mod+2;
init(n);
for (int i=1;i<n;i++)
{
int x=read(),y=read();
addedge(x,y);
addedge(y,x);
}
getroot(1,0); //求重心
if (mx[root2]==ymh)
{
root=n+1;
for (int i=point[root1];i;i=nxt[i])
{
int p = to[i];
if (p==root2)
{
to[i]=to[i^1]=n+1;
break;
}
}
addedge(root,root1);
addedge(root,root2);
}
else
{
root = root1;
}
// cout<<root<<endl;
memset(size,0,sizeof(size));
dfs(root,0);
dfs1(root,0);
// cout<<1<<endl;
solve(root,0);
//cout<<root<<endl;
//cout<<root1<<" "<<root2<<endl;
//cout<<1<<endl;
if (root==root1)
{
//cout<<"****"<<endl;
cout<<(dp[root][0]+dp[root][1])%mod;
return 0;
}
int ans=0;
if (ha[root1]==ha[root2])
{
int p = dp[root2][0]%mod;
ans=(dp[root1][1]*dp[root2][0]%mod+C(p+2-1,2))%mod;
}
else
{
//cout<<"*****************"<<endl;
ans=(dp[root1][1]*dp[root2][0]%mod+dp[root1][0]*dp[root2][1]%mod+dp[root1][0]*dp[root2][0]%mod)%mod;
}
cout<<ans;
return 0;
}
最新文章
- SQL优化技术分析-1：操作符优化
- objective-c 语法快速过（8）
- HTML5+CSS3 - 代码简写篇
- MySQL 在 LIMIT 条件后注入
- 华硕Z97-A主板声卡设置
- C#参考：Linq 概述
- jquery在线预览PDF文件，打开PDF文件(向下兼容ie8、ie7)
- 使用 MNIST 图像识别数据集
- 从汇编看c++内联函数评估求值
- 函数之return
- 实例化vue之前赋值html元素导致事件失效
- Struts2 xml 详解
- spring的基于注解的IOC配置
- 使用百度ocr接口识别验证码
- Running tests on PyCharm using Robot Framework
- いろはちゃんとマス目 / Iroha and a Grid （组合数学）
- 峰Redis学习（7）Redis 持久化RDB方式
- Spring之配置文件中引入其它配置文件
- Codeforces 431C - k-Tree
- 一步一步学习IdentityServer3 (14) 启用Https