BZOJ 3162:独釣寒江雪(Hash判断樹同構造+樹形DP+組合せ数学)
タイトル転送ゲート:http://www.lydsy.com/JudgeOnline/problem.php?id=3162
タイトル分析:すごい問題で、Hashが2本の木の形態が同じかどうかを判断できることを知らせました.
この問題の具体的なやり方はVFKの問題解を見てみましょう.orzしかできないと思います.簡単な言葉で問題解を要約すると、
1.重心がツリーの直径の中点であることを定義します.ツリーの直径の長さが偶数の場合は、真ん中のエッジに重心として虚点を追加します.2.重心を根として根木があるようになり、括弧配列Hash+を並べて2本の木が同構造であるか否かを判断する.3.ある点のすべての息子のサブツリー集合をΣx(cx,nx)Σx(cx,nx)とし、そのうち(ci,ni)(c i,n i)はci c iの形態を表すサブツリーにni n i本がある.異なる形態のサブツリーは互いに影響しないため,問題は(ci,ni)(c i,n i)の現在のノードへの寄与をどのように計算するかとなる.組合せ数による値域が[1,n][1,n]のm個数の組合せスキームはCmn+m−1 Cn+m−1 Cn+m−1 mである.4.各点に2つの値f,g f,gを設定し、それぞれこの点を選択または選択しない場合のサブツリーのシナリオ数を表す.それから数学+DPを組み合わせて、分類して討論してメンテナンスすることができます.
最後に私が知っている組み合わせ数についていくつかのものをまとめます:1 n個の異なるボールをm個の異なる箱に入れます:mn m n.2 n個の同じボールをm個の異なる箱に入れる:すべての箱とボールを任意に乱して一列に並べ、最後の1つを必ず箱にし、それから各箱の前の1つの箱からその間のボールを獲得し、最後にすべての箱に対して左から右に1~m番号をつける.このようなスキーム数はCm−1 n+m−1 Cn+m−1 Cn+m−1 m−1であることが分かる.③値域が[1,n]のm個数の組合せ案数:m個の同じ数を1~nのn個の集合に直接見て、②とする.VFKのpdfには、a 1≦a 2......≦am a 1≦a 2......≦a mとすると、a 1+1最後に、この問題の注意点についてお話しします。首先、Hash値を切り出す場合、大きな値を前に並べます。これは深さの大きいポイントの重さが大きくなり、衝突が難しくなります。また、2本の木が同構造であるか否かを判断するには、Hash値が等しくないだけです。f,g f,判断g值等,可以降低冲突的确率。如果原木的重心一侧的话,左右的2条木是否判断该构造呐?请注意。这个问题的样子很强,所以应该是过了桑普尔的话1 A。ODE:#include #include #include #include #include #include #include #include #include using namespace std; const int maxn=500100; const long long M=1000000007; typedef long long LL; struct edge { int obj; edge *Next; } e[maxn<<1]; edge *head[maxn]; int cur=-1; LL Two[maxn]; LL nfac[maxn]; LL Hash_val[maxn]; int Len[maxn]; vector <int> Son[maxn]; LL f[maxn]; LL g[maxn]; int d[maxn]; int len; int fa[maxn]; int dep[maxn]; int n; void Add(int x,int y) { cur++; e[cur].obj=y; e[cur].Next=head[x]; head[x]=e+cur; } void Find(int node) { for (edge *p=head[node]; p; p=p->Next) { int son=p->obj; if (son==fa[node]) continue; fa[son]=node; dep[son]=dep[node]+1; Find(son); } } bool Comp(int x,int y) { return (Hash_val[x]>Hash_val[y]); } bool Judge(int x,int y) { return ( Hash_val[x]==Hash_val[y] && f[x]==f[y] && g[x]==g[y] ); } LL Get(LL n,LL m) { n=n+m-1LL; LL ans=1; for (LL i=0; ireturn ans; } void Work(int node,int Fa) { Len[node]=0; f[node]=g[node]=1; for (edge *p=head[node]; p; p=p->Next) { int son=p->obj; if (son==Fa) continue; Son[node].push_back(son); Work(son,node); } if (!Son[node].size()) { Len[node]=2; Hash_val[node]=1; } else { int k=Son[node].size(); sort(Son[node].begin(),Son[node].begin()+k,Comp); Len[node]=1; LL &v=Hash_val[node]; v=0; for (int i=0; iint x=Son[node][i]; v=(v*Two[ Len[x] ]%M+Hash_val[x])%M; } v=((v<<1)|1)%M; int head=0; while (headint tail=head; int x=Son[node][head]; while ( tailint num=tail-head; f[node]=f[node]*Get(g[x],num)%M; g[node]=g[node]*Get( (f[x]+g[x])%M ,num)%M; head=tail; } } } int main() { freopen("3162.in","r",stdin); freopen("3162.out","w",stdout); scanf("%d",&n); for (int i=1; i<=n; i++) head[i]=NULL; for (int i=1; iint x,y; scanf("%d%d",&x,&y); Add(x,y); Add(y,x); } dep[1]=1; Find(1); int root=1; for (int i=2; i<=n; i++) if (dep[i]>dep[root]) root=i; fa[root]=0; dep[root]=1; Find(root); int bot=1; for (int i=2; i<=n; i++) if (dep[i]>dep[bot]) bot=i; len=0; while (bot!=root) d[++len]=bot,bot=fa[bot]; d[++len]=root; nfac[0]=nfac[1]=1; for (int i=2; i<=n; i++) { LL x=M/i,y=M%i; nfac[i]=M-x*nfac[y]%M; } for (int i=1; i<=n; i++) nfac[i]=nfac[i-1]*nfac[i]%M; Two[0]=1; for (int i=1; i<=n; i++) Two[i]=(Two[i-1]<<1)%M; if (len&1) { root=d[(len+1)>>1]; Work(root,0); f[root]=(f[root]+g[root])%M; printf("%I64d",f[root]); } else { root=d[len>>1]; bot=d[(len>>1)+1]; Work(root,bot); Work(bot,root); LL ans; if ( Judge(bot,root) ) ans=(Get( (f[bot]+g[bot])%M ,2LL)-Get(f[bot],2LL)+M)%M; else ans=(f[bot]*g[root]%M+g[bot]*f[root]%M+g[bot]*g[root]%M)%M; printf("%I64d",ans); } return 0; }
タイトル分析:すごい問題で、Hashが2本の木の形態が同じかどうかを判断できることを知らせました.
この問題の具体的なやり方はVFKの問題解を見てみましょう.orzしかできないと思います.簡単な言葉で問題解を要約すると、
1.重心がツリーの直径の中点であることを定義します.ツリーの直径の長さが偶数の場合は、真ん中のエッジに重心として虚点を追加します.2.重心を根として根木があるようになり、括弧配列Hash+を並べて2本の木が同構造であるか否かを判断する.3.ある点のすべての息子のサブツリー集合をΣx(cx,nx)Σx(cx,nx)とし、そのうち(ci,ni)(c i,n i)はci c iの形態を表すサブツリーにni n i本がある.異なる形態のサブツリーは互いに影響しないため,問題は(ci,ni)(c i,n i)の現在のノードへの寄与をどのように計算するかとなる.組合せ数による値域が[1,n][1,n]のm個数の組合せスキームはCmn+m−1 Cn+m−1 Cn+m−1 mである.4.各点に2つの値f,g f,gを設定し、それぞれこの点を選択または選択しない場合のサブツリーのシナリオ数を表す.それから数学+DPを組み合わせて、分類して討論してメンテナンスすることができます.
最後に私が知っている組み合わせ数についていくつかのものをまとめます:1 n個の異なるボールをm個の異なる箱に入れます:mn m n.2 n個の同じボールをm個の異なる箱に入れる:すべての箱とボールを任意に乱して一列に並べ、最後の1つを必ず箱にし、それから各箱の前の1つの箱からその間のボールを獲得し、最後にすべての箱に対して左から右に1~m番号をつける.このようなスキーム数はCm−1 n+m−1 Cn+m−1 Cn+m−1 m−1であることが分かる.③値域が[1,n]のm個数の組合せ案数:m個の同じ数を1~nのn個の集合に直接見て、②とする.VFKのpdfには、a 1≦a 2......≦am a 1≦a 2......≦a mとすると、a 1+1最後に、この問題の注意点についてお話しします。首先、Hash値を切り出す場合、大きな値を前に並べます。これは深さの大きいポイントの重さが大きくなり、衝突が難しくなります。また、2本の木が同構造であるか否かを判断するには、Hash値が等しくないだけです。f,g f,判断g值等,可以降低冲突的确率。如果原木的重心一侧的话,左右的2条木是否判断该构造呐?请注意。这个问题的样子很强,所以应该是过了桑普尔的话1 A。ODE:#include #include #include #include #include #include #include #include #include using namespace std; const int maxn=500100; const long long M=1000000007; typedef long long LL; struct edge { int obj; edge *Next; } e[maxn<<1]; edge *head[maxn]; int cur=-1; LL Two[maxn]; LL nfac[maxn]; LL Hash_val[maxn]; int Len[maxn]; vector <int> Son[maxn]; LL f[maxn]; LL g[maxn]; int d[maxn]; int len; int fa[maxn]; int dep[maxn]; int n; void Add(int x,int y) { cur++; e[cur].obj=y; e[cur].Next=head[x]; head[x]=e+cur; } void Find(int node) { for (edge *p=head[node]; p; p=p->Next) { int son=p->obj; if (son==fa[node]) continue; fa[son]=node; dep[son]=dep[node]+1; Find(son); } } bool Comp(int x,int y) { return (Hash_val[x]>Hash_val[y]); } bool Judge(int x,int y) { return ( Hash_val[x]==Hash_val[y] && f[x]==f[y] && g[x]==g[y] ); } LL Get(LL n,LL m) { n=n+m-1LL; LL ans=1; for (LL i=0; ireturn ans; } void Work(int node,int Fa) { Len[node]=0; f[node]=g[node]=1; for (edge *p=head[node]; p; p=p->Next) { int son=p->obj; if (son==Fa) continue; Son[node].push_back(son); Work(son,node); } if (!Son[node].size()) { Len[node]=2; Hash_val[node]=1; } else { int k=Son[node].size(); sort(Son[node].begin(),Son[node].begin()+k,Comp); Len[node]=1; LL &v=Hash_val[node]; v=0; for (int i=0; iint x=Son[node][i]; v=(v*Two[ Len[x] ]%M+Hash_val[x])%M; } v=((v<<1)|1)%M; int head=0; while (headint tail=head; int x=Son[node][head]; while ( tailint num=tail-head; f[node]=f[node]*Get(g[x],num)%M; g[node]=g[node]*Get( (f[x]+g[x])%M ,num)%M; head=tail; } } } int main() { freopen("3162.in","r",stdin); freopen("3162.out","w",stdout); scanf("%d",&n); for (int i=1; i<=n; i++) head[i]=NULL; for (int i=1; iint x,y; scanf("%d%d",&x,&y); Add(x,y); Add(y,x); } dep[1]=1; Find(1); int root=1; for (int i=2; i<=n; i++) if (dep[i]>dep[root]) root=i; fa[root]=0; dep[root]=1; Find(root); int bot=1; for (int i=2; i<=n; i++) if (dep[i]>dep[bot]) bot=i; len=0; while (bot!=root) d[++len]=bot,bot=fa[bot]; d[++len]=root; nfac[0]=nfac[1]=1; for (int i=2; i<=n; i++) { LL x=M/i,y=M%i; nfac[i]=M-x*nfac[y]%M; } for (int i=1; i<=n; i++) nfac[i]=nfac[i-1]*nfac[i]%M; Two[0]=1; for (int i=1; i<=n; i++) Two[i]=(Two[i-1]<<1)%M; if (len&1) { root=d[(len+1)>>1]; Work(root,0); f[root]=(f[root]+g[root])%M; printf("%I64d",f[root]); } else { root=d[len>>1]; bot=d[(len>>1)+1]; Work(root,bot); Work(bot,root); LL ans; if ( Judge(bot,root) ) ans=(Get( (f[bot]+g[bot])%M ,2LL)-Get(f[bot],2LL)+M)%M; else ans=(f[bot]*g[root]%M+g[bot]*f[root]%M+g[bot]*g[root]%M)%M; printf("%I64d",ans); } return 0; }