出题人你卡 hash 卡得开心吗?
Part1. 题面 本题有多组数据,总共 $t$ 组。
每组数据给出一棵 $n$ 个点的无根树,求从任意点出发可能得到的本质不同的括号序列数量,对 $998244353$ 取模。
> Tip 一棵树的括号序列为:从根节点出发 DFS,当一个点进入 DFS 栈中时,在序列的末尾加上 (
,当一个点从 DFS 栈中弹出时,在序列末尾加上 )
。 这样可以得到一个长度为 2n 的括号序列。 本质不同的括号序列即指长得不一样的括号序列。
数据结构 :$1\le t\le10^5,1\le n\le10^5$;保证所有数据点的 $n$ 之和不超过 $3.2\times10^6$。
Part2. 解析 首先你得知道什么叫树的同构:
> Tip 如果两棵树可以通过给节点重新编号,使得两棵树对应边的节点编号相同,则称这两棵树同构。
Part2/1. 指定某点为根的答案 不妨指定 1 为根。(万年工具人 1 号节点……)
可以直接 dp:u 的子树中的括号序列数量为 f[u]
;
> Tab cntch[u]
为 u 的子节点数量;fac[i]
为模意义下的 $i!$。
先计算出每个子节点的答案 f[v]
:
f[u]
应该为所有 f[v]
的乘积(因为是方案数,所以通过乘法原理计算);
DFS 子树的顺序也会造成影响,所以要乘上子树的全排列,即乘上 fac[cntch[u]]
;
不难发现,同构的两棵树的括号序列的方案集合一定是一样的 ,因此有一些会算重复;
把同构的子树划分到一块,计算出每一块的大小,为 $\{sam_1,sam_2,…,sam_t\}$,那么最后应该除以 $\prod_{i=1}^t(sam_i)!$。(其实就是可重集的全排列)
最后得到的转移式(要在模意义下计算):
Part2/2. 换根DP求树的同构 (这也是最近学习的内容 awa)
仍然先考虑指定 1 号节点为根,求出树的一个 hash 值。可以考虑这样设计一个 hash 的递归式:
> Tab 以下默认以 1 为整棵树的根
$idx_u$ 表示以 u 为根的子树的 hash 值。对于叶子节点 $idx_u=1$;其他节点的计算方式为 $idx_u=1+\sum_{v}idx_v\times rand_{siz_v}$,其中 $rand$ 是一开始随机化得到的一个数列 ,$siz_v$ 是以 v 为根的子树的大小。这样可以一次 DFS 求出每个点的 $idx$。
为什么这样设计 hash?当然目的是要让它的冲突尽可能少。理论上当 $rand$ 数列取质数数列的时候可以尽可能地避免冲突,但是我们需要的 $rand$ 比较多,找质数序列反而麻烦了,于是交给随机化。:)
这样我们就求得了这棵树以 1 为根的 hash 值,但是我们发现当这棵树以不同的点作为根时,hash 值可能不同。为了相对准确地判断树的同构,我们可以在求出以 1 为根的 $idx$ 的基础上,通过 换根DP 计算出以每一个点 $u$ 为根的 $idx’_u$ 。
考虑从当前的根 $u$ 将根换到子节点 $v$。换根DP的核心就是“一次换根只会影响 u 和 v 的DP值 ”,显然 $idx_u’$ 是满足这个特点的。
考虑从 u 到 v 的转移:
我们已经计算出了 $idx’_u$,要计算 $idx_v’$。发现 v 的子树内的 $idx_v$ 并没有改变,换根后,u 变为 v 的子节点。首先 u 要减去原来 v 对 $idx_u’$ 的贡献:$rand_{siz_v}\times idx_v$,然后 v 要加上 u 的贡献 $(idx_u’-rand_{siz_v}\times idx_v)\times rand_{n-siz_v}$($n-siz_v$ 就是现在 u 的子树的大小嘛)。
所以可以得到 $idx’_v=idx_v+(idx_u’-rand_{siz_v}\times idx_{siz_v})\times rand_{n-siz_v}$,最初 $idx’_1=idx_1$,然后就可以 DP 了。
实际上,实现代码时,$idx’_v$ 并没有加上 $idx_v$,而是 $idx’_v=idx_u-rand_{siz_v}\times idx_{siz_v}+rand_{n-siz_u}\times idx_u’$。当要计算以 v 为根的 hash 值时,就计算 $idx’_v\times rand_{n-siz_v}+idx_v$ 即可。
Part2/3. 换根DP求每个点为根的答案 在 Part2/1 ,我们DP计算了以 1 为根的答案,但是显然以不同的点为根,括号序列很有可能是不一样的。
其实和换根DP求 $idx_u’$ 是差不多的,还是定义 $f’_u$ 表示整棵树以 u 为根,能够得到的本质不同的括号序列的数量。主要难点就是“删去 v 对 $f_u’$ 的贡献,并计算新的作为 v 的子节点的 u 的贡献”。
记删去 v 对 $f’_u$ 的贡献后,u 作为 v 的子节点代表的子树中括号序列的数量为 $h$。最初将 $h$ 的值设为 $f’_u$
要删除贡献,首先要知道 $f_u’$ 是怎么计算的:
v 不是 u 的子树了,要除去 $f_v$ 对 $f_u’$ 的贡献,即$\div f_v$;
u 的子树少了一棵:记原来 u 作为根时,有 cnt 棵子树,因为计算的时候 $f_v$ 中乘上了 $cnt!$,现在要改为乘上 $(cnt-1)!$ —— 可以先乘上 $(cnt!)^{-1}$ 再乘上 $(cnt-1)!$ ;
u 的子树中,与 v 同构的子树少了一棵:设原来 u 为根时,与 v 同构的子树有 $sam$ 棵,因为要除去重复,除掉了 $sam!$,现在要改为除掉 $(sam-1)!$ —— 可以先乘上 $sam!$,再乘上 $\left[(sam-1)!\right]^{-1}$;
所以 $h=f_u’\times (f_v)^{-1}\times (cnt!)^{-1}\times(cnt-1)!\times sam!\times (sam-1)!$;这样 u 作为 v 的子树时的括号序列数量就求到了。
然后计算 $f_v’$,先设 $f_v’$ 的初值为 $f_v$:(仍然是这张图)
u 作为 v 的子树,提供了 $h$ 的贡献,则乘上 $h$;
v 的子树多了一个,记原来子树个数为 $cnt_v$,因为全排列时乘上了 $cnt_v!$,现在要乘上 $(cnt_v+1)!$,所以乘上 $(cnt_v+1)$ 即可;
v 的与 u 同构的子树增加了一个(这里 u 的子树的哈希值就是 $idx_v’$ 了),记原来 u 的与 u 同构的子树个数为 $sam_v$,因为去重时除去了 $sam_v!$,现在要除去 $(sam_v+1)!$ —— 则先乘上 $sam_v!$,再乘上 $[(sam_v+1)!]^{-1}$ 。
可得 $f_v’=f_v\times h\times (cnt_v+1)\times sam_v!\times [(sam_v+1)!]^{-1}$;
Part2/4. 统计答案 已经计算出分别以每个点为根的答案了,似乎直接把 $f_u’$ 加起来就可以了。
但是一样的道理,如果以 u 为根的整棵树与以 v 为根的整棵树形态相同,那么它们的括号序列方案集合一定完全相同,所以只能计算一次。这个就用到整棵树的哈希值。
还好之前已经计算了,以 u 为根的整棵树的哈希值就为 $idx_u+idx’_u\times rand_{n-siz_u}$。所以只要 map 或者 set 判一下重就好了。
> Tip 这道题卡哈希!(好端端的一道哈希题被搞成了一道rp题……) 反正我写了一个三哈希……用结构体打了包,可以参考一下。
Part3. 源代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 #include <set> #include <map> #include <vector> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std ;typedef unsigned long long ull;typedef unsigned int uint;const int N=1e5 ;const int MOD=998244353 ;#define fix(x) (int((x%MOD+MOD)%MOD)) struct MNUM { int num; MNUM(){} MNUM(int _n){num=_n;} MNUM operator +(const MNUM &B)const {return fix(1l l*num+B.num);} MNUM operator -(const MNUM &B)const {return fix(1l l*num-B.num);} MNUM operator *(const MNUM &B)const {return fix(1l l*num*B.num);} MNUM operator +=(const MNUM &B){return *this =(*this )+B;} MNUM operator -=(const MNUM &B){return *this =(*this )-B;} MNUM operator *=(const MNUM &B){return *this =(*this )*B;} MNUM operator <(const MNUM &B)const {return num<B.num;} }fac[N+3 ],ifac[N+3 ],ansf[N+3 ],ansg[N+3 ],ans; struct TNODE { int to;TNODE *nxt; TNODE(){} TNODE(int _t ,TNODE *_n):to(_t ),nxt(_n){} }; struct TREE { TNODE pol[N*2 +3 ],*head[N+3 ],*ncnt; void Init (int n) { ncnt=pol; for (int u=1 ;u<=n;u++) head[u]=NULL ; } void AddEdge (int u,int v) { TNODE *p=++ncnt,*q=++ncnt; *p=TNODE(v,head[u]);head[u]=p; *q=TNODE(u,head[v]);head[v]=q; } TNODE* operator [](int id){return head[id];} }T_; const ull HASHMOD1=1073790841 ,HASHMOD2=1073919029 ,HASHMOD3=2305843009213693951u ll;struct HASH { ull idx1,idx2,idx3; HASH(){} HASH(ull A){idx1=idx2=idx3=A;} HASH(ull Ix1,ull Ix2,ull Ix3):idx1(Ix1%HASHMOD1),idx2(Ix2%HASHMOD2),idx3(Ix3%HASHMOD3){} ull& operator [](int id){return id==1 ? idx1:idx2;} HASH operator *(const HASH &B)const {return HASH(idx1*B.idx1,idx2*B.idx2,idx3*B.idx3);} HASH operator -(const HASH &B)const {return HASH(idx1+HASHMOD1-B.idx1,idx2+HASHMOD2-B.idx2,idx3+HASHMOD3-B.idx3);} HASH operator +(const HASH &B)const {return HASH(idx1+B.idx1,idx2+B.idx2,idx3+B.idx3);} HASH operator *=(const HASH &B){return *this =(*this )*B;} HASH operator -=(const HASH &B){return *this =(*this )-B;} HASH operator +=(const HASH &B){return *this =(*this )+B;} bool operator <(const HASH &B)const { if (idx1!=B.idx1) return idx1<B.idx1; if (idx2!=B.idx2) return idx2<B.idx2; return idx3<B.idx3; } bool operator !=(const HASH &B)const {return idx1!=B.idx1 || idx2!=B.idx2 || idx3!=B.idx3;} bool operator ==(const HASH &B)const {return idx1==B.idx1 && idx2==B.idx2 && idx3==B.idx3;} }idxf[N+3 ],idxg[N+3 ],rnd[N+3 ],nidxg[N+3 ]; int n,cas;int siz[N+3 ],cntch[N+3 ];set < HASH > cont;map < HASH,int > per[N+3 ];MNUM QPow (MNUM und,int ovr) { MNUM resu (1 ) ; while (ovr){ if (ovr&1 ) resu*=und; und*=und; ovr>>=1 ; } return resu; } void DFSf (int u,int fa) { vector < HASH > sav; idxf[u]=HASH(1 ); siz[u]=1 ;ansf[u]=1 ; cntch[u]=0 ; for (TNODE *it=T_[u];it;it=it->nxt){ int v=it->to; if (v==fa) continue ; cntch[u]++; DFSf(v,u); siz[u]+=siz[v]; idxf[u]+=rnd[siz[v]]*idxf[v]; ansf[u]*=ansf[v]; sav.push_back(idxf[v]); per[u][idxf[v]]++; } ansf[u]*=fac[cntch[u]]; sort(sav.begin(),sav.end()); int cnt=1 ; for (int i=1 ;i<(int )sav.size();i++) if (sav[i]!=sav[i-1 ]){ ansf[u]*=ifac[cnt]; cnt=1 ; } else cnt++; ansf[u]*=ifac[cnt]; } void DFSg (int u,int fa) { for (TNODE *it=T_[u];it;it=it->nxt){ int v=it->to; if (v==fa) continue ; idxg[v]=idxf[u]-rnd[siz[v]]*idxf[v]+rnd[n-siz[u]]*idxg[u]; int cntsam=per[u][idxf[v]]; if (u!=1 && idxg[u]==idxf[v]) cntsam++; int nch=cntch[u]; if (u!=1 ) nch++; MNUM resu=ansg[u]; resu*=fac[cntsam];resu*=ifac[cntsam-1 ]; resu*=ifac[nch];resu*=fac[nch-1 ]; resu*=QPow(ansf[v],MOD-2 ); cntsam=per[v][idxg[v]]+1 ; nch=cntch[v]+1 ; ansg[v]=ansf[v]; ansg[v]*=resu; ansg[v]*=ifac[nch-1 ];ansg[v]*=fac[nch]; ansg[v]*=fac[cntsam-1 ];ansg[v]*=ifac[cntsam]; DFSg(v,u); } HASH rel=idxf[u]+idxg[u]*rnd[n-siz[u]]; if (!cont.count(rel)){ cont.insert(rel); ans+=ansg[u]; } } void Init () { fac[0 ]=1 ; for (int i=1 ;i<=N+2 ;i++) fac[i]=fac[i-1 ]*i; ifac[N+2 ]=QPow(fac[N+2 ],MOD-2 ); for (int i=N+1 ;i>=0 ;i--) ifac[i]=ifac[i+1 ]*(i+1 ); } int main () { Init(); scanf ("%d" ,&cas); srand(20192022 ); for (int i=0 ;i<=N+2 ;i++){ rnd[i][0 ]=(i? rnd[i][2 ]:0 )+(ull)rand()*(ull)rand(); rnd[i][1 ]=(i? rnd[i][0 ]:0 )+(ull)rand()*(ull)rand(); rnd[i][2 ]=(i? rnd[i][1 ]:0 )+(ull)rand()*(ull)rand(); } while (cas--){ scanf ("%d" ,&n); cont.clear(); ans=0 ; T_.Init(n); for (int i=1 ;i<=n;i++){ per[i].clear(); idxf[i]=idxg[i]=nidxg[i]=HASH(0 ); ansf[i]=ansg[i]=0 ; } for (int i=1 ;i<n;i++){ int u,v; scanf ("%d%d" ,&u,&v); T_.AddEdge(u,v); } DFSf(1 ,0 ); ansg[1 ]=ansf[1 ]; DFSg(1 ,0 ); printf ("%d\n" ,ans.num); } return 0 ; }
The End Thanks for reading! 明明一道好好的哈希判断树的同构题为什么非要卡哈希卡成这样…… =_=