【May】
【Codeforces 438E】The Child and Binary Tree
递推式的优化处理(FFT,按照时间分治)
2013集训队互测的城市规划
优化递推式的计算(F已经计算):\( G_{n} = \sum_{i=1}^{n-1} G_{i} * F_{n-i} \)
直接计算G的值的时间复杂度是平方级别的。但经过观察,整个式子是卷积形式的,使用FFT(快速傅里叶变换)可以优化计算时间复杂度。
但瓶颈是:G的计算依赖于G。如果式子是\( G_{n} = \sum_{i=1}^{n-1} F_{i} * F_{n-i} \),则是一个很基础的问题了。在G里的元素尚未确定的情况下,是不能够直接套用FFT的。
解决问题的方式是按照时间分治。类似于CDQ分治,计算前一段(已经计算的)对后一段(正在计算的)的贡献。
实现的方法如下:
- 定义SOLVE(l,r)为计算 \( G_{l} \cdots G_{r} \)的值。
- 定义mid = (l+r)/2。递归处理SOLVE(l, mid), 处理完成后,这是l到mid的G值都计算完毕了。
- 下面计算(l,mid)对(mid+1,r)的贡献。即,计算\( T_{n} = \sum_{i=l}^{mid} G_{i} * F_{n-i} \),T为(l,mid)的每一项对(mid+1,r)的每一项的贡献,这一部分可以使用FFT进行优化(卷积形式)。
- 处理SOLVE(mid+1, r)。
每两个位置i,j(i<j),他们之间的影响被分到了每一层计算,累加则能得到结果,总时间复杂度为\( O(NLog^{2}N)\)。
Codeforces 438E : The Child and Binary Tree
优化递推式的计算(C已经计算):\( G_{n} = \sum_{i=0}^{n-1} \sum_{j=0}^{n-i} C_{i} * G_{j} * G_{n-i-j} \)
这道题的瓶颈是G的计算需要更加细节的处理。在一些时候需要两倍计算:因为(i,j)与(j,i)都会对n产生影响,而只会在i<j的时候计算,所以在区间不相交的时候需要计算两次。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int N = 6e5 + 5; int Mod = 998244353; int n, m, l, lm, x[N]; int tr[20][N], wi[20][N]; int a[N], ci; int b[N], c[N], d[N], tp[N]; int pow(int a, int b) { LL r(1), s(a); for(; b; b>>=1, s=s*s%Mod) if(b&1) r=r*s%Mod; return r; } void maketh(int L, int lm, int *tr, int *wi) { for(int i=0, p, j, k; i<l; tr[i++] = p) for(p=0, j=i, k=0; k<lm; k++, j>>=1) p = (p<<1) + (j&1); wi[0] = 1, wi[1] = pow(3, (Mod-1) / l); for(int i=2; i<=l; i++) wi[i] = LL(wi[i-1]) * wi[1] % Mod; } void makett(int L) { l=L, ci = pow(l, Mod-2); } void dft(int *a, int sig, int *tr, int *wi) { for(int i=0; i<l; i++) tp[tr[i]] = a[i]; int bei = l, hal, lei; for(int i=2; i<=l; i+=i) { hal = i>>1, lei = sig>0?0:l, bei>>=1; for(int j=0; j<hal; j++, lei+=bei*sig) for(int k=j, w=wi[lei]; k<l; k+=i) { int u=tp[k], v=LL(tp[k+hal])*w%Mod; tp[k] = (u+v) % Mod; tp[k+hal] = (u-v+Mod) % Mod; } } for(int i=0; i<l; i++) a[i]=tp[i]; } void solve(int l, int r) { if(l==r) return; int m = (l+r)>>1, lg = r-l, L; solve(l, m); for(L = 1, lm = 0; L <= lg * 2; L += L, ++lm); makett(L); for(int i=0; i<L; i++) b[i] = c[i] = d[i] = 0; for(int i=l; i<=m; i++) b[i-l] = a[i]; for(int i=0; i<=lg; i++) c[i] = x[i]; // DETAIL if(lg<=l) for(int i=0; i<=lg; i++) d[i] = (a[i] + a[i]) % Mod; else for(int i=l; i<=m; i++) d[i-l] = a[i]; dft(b, 1, tr[lm], wi[lm]), dft(c, 1, tr[lm], wi[lm]), dft(d, 1, tr[lm], wi[lm]); for(int i=0; i<L; i++) b[i] = LL(b[i]) * c[i] % Mod * d[i] % Mod; dft(b, -1, tr[lm], wi[lm]); for(int i=0; i<L; i++) b[i] = LL(b[i]) * ci % Mod; for(int i=m+1; i<=r; i++) (a[i] += b[i-l]) %= Mod; solve(m+1, r); } int main() { scanf("%d%d", &n, &m), a[0] = 1; for(int i=1, p; i<=n; i++) scanf("%d", &p), x[p] = 1; for(l=1, lm=0; l <= m*3; l+=l, ++lm) maketh(l, lm, tr[lm], wi[lm]); maketh(l, lm, tr[lm], wi[lm]); solve(0, m); for(int i=1; i<=m; i++) printf("%d\n", int(a[i])); return 0; }
【Codeforces 343E】Pumping Stations(Gomory-Hu Tree的定义与构建)
定义
WIKI:一个带权无向图G(V,E)的Gomory-Hu树,代表了图中所有s-t最小割。使用V-1次最小割可以构建出Gomory-Hu树。
简单的来说,树上的两点之间的路径最小值,就是在原图中两点的最小割。
构建
- 我们一开始将所有点的父亲指向1。
- 枚举每一个点i,计算它和父亲fi的最小割,并连边。
- 再枚举对于点j,若满足fj=fi并且j与i在最小割的一边,那么把fj=i
实现
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 205; const int M = 1005; int n, m, v[N], fa[N], f[N]; namespace netw { const int P = N; const int E = M + M; const int inf = 1e9; int to[E], next[E], end[P], f[E], tms; void link(int x, int y, int z) { to[++tms]=y, next[tms]=end[x], end[x]=tms, f[tms]=z; to[++tms]=x, next[tms]=end[y], end[y]=tms, f[tms]=z; } int dat[P], pred[P], cur[P], cnt[P], dist[P]; int sap(int S, int T) { for(int i=1; i<=n; i++) dist[i]=1, cnt[i]=0, cur[i]=end[i]; dat[S]=inf, dist[T]=0, cnt[1]=n-1, cnt[0]=1; int x(S), p, q, ret(0); for(;;) { for(p=cur[x]; p; p=next[p]) if(f[p]>0 && dist[to[p]]+1==dist[x]) break; if(p) { dat[to[p]]=min(dat[x],f[p]), pred[to[p]]=p, cur[x]=p, x=to[p]; if(x==T) for(ret+=dat[T]; x!=S; x=to[pred[x]^1]) f[pred[x]]-=dat[T], f[pred[x]^1]+=dat[T]; } else { if(--cnt[dist[x]]==0) return ret; for(dist[x]=n+1, q=end[x]; q; q=next[q]) if(f[q]>0 && dist[to[q]]+1<dist[x]) dist[x]=dist[to[q]]+1, cur[x]=q; ++cnt[dist[x]]; if(dist[S]>n) return ret; if(x^S) x=to[pred[x]^1]; } } } void paint(int x, int *v) { if(v[x]) return; v[x]=1; for(int p=end[x]; p; p=next[p]) if(f[p]) paint(to[p], v); } void bfs(int x, int *v) { for(int i=1; i<=n; i++) v[i] = 0; paint(x, v); for(int i=2, j; i<=tms; i+=2) j = f[i] + f[i+1], f[i] = f[i+1] = j / 2; } } int to[N+N], next[N+N], end[N], d[N+N], fv[N+N], tms; int per[N], cp; void cgg(int x, int fa) { for(int p=end[x]; p; p=next[p]) if(!fv[p] && to[p]!=fa) { if(!cp || d[p]<d[cp]) cp=p; cgg(to[p], x); } } void sp(int x) { int u(1), tp; for(int p=end[x]; p && u; p=next[p]) if(!fv[p]) u=0; if(u) {per[++per[0]] = x; return;} cp=0, cgg(x, 0), fv[cp] = fv[cp^1] = 1; tp=cp, sp(to[tp]), sp(to[tp^1]); } int main() { scanf("%d%d", &n, &m), netw :: tms = 1; for(int i=1, x, y, z; i<=m; i++) { scanf("%d%d%d", &x, &y, &z); netw :: link(x, y, z); } for(int i=1; i<=n; i++) fa[i] = 1; for(int i=2; i<=n; i++) { f[i] = netw :: sap(i, fa[i]), netw :: bfs(i, v), f[0] += f[i]; for(int j=i+1; j<=n; j++) if(v[j] && fa[j] == fa[i]) fa[j] = i; } // Gomory-Hu Tree 的 中心构造过程 tms = 1; for(int i=2; i<=n; i++) { to[++tms]=i, next[tms]=end[fa[i]], end[fa[i]]=tms, d[tms]=f[i]; to[++tms]=fa[i], next[tms]=end[i], end[i]=tms, d[tms]=f[i]; } sp(1); printf("%d\n", f[0]); for(int i=1; i<n; i++) printf("%d ", per[i]); printf("%d\n", per[n]); return 0; }
应用
Codeforces 343E:找出一个排列,使得相邻两项的最小割之和最大
最小割之和就是树上的边权总和:找出在Gomory-Hu树上的最大边权的一条边,假如它连接的是u与v,那么排列中u与v必定是相邻的,不然就会浪费这条边权了。这样分析下来,每一条边权都会取到,而这是能够达到的上界。
下面分析如何得到一组合法的解。找出树上一条边权最小的边,把树分为两半,递归处理,把两边的答案合并就可以了。这样做是可以达到上界的,因为最大的边必定会留到最后,而最小的边权由于约束最松,可以最先处理。
UVA 11594 : All Pairs Maximum Flow
直接套用构建的模板就可以。
UVA 11603 : Its all about the Bandwidth /HDU 4700 : FLOW
给出N点之间的最小割,构建出图G满足其约束。
一个合法的G必能转化成一个合法的Gomory-Hu树,所以直接构建一棵树就好了。找出其中一条最短的边L,将树分成两半A与B:A与B之间最小割均为边权L则合法,递归处理。(如何分割A与B?固定其中一个点X在A,与X的最小割值大于L则只能在A,否则放置于B)为什么这个算法一定能得到正确解呢?
【POJ 3986】Math Teacher's Homework
一道比较有趣的数位DP
【POJ 1777】Vivian's Problem
梅森素数的应用