【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
梅森素数的应用