In mathematics you don't understand things, you just get used to them.

破壁,组合意义法:

五种颜色 $\star,a,b,c,d$。

  • 对于 l.h.s.

钦定 $k$,在 $3n+k$ 个球中选出 $2n$ 个球染色,在靠左的 $n$ 个球中选 $k$ 个染成 $a$ 色,剩余 $n-k$ 个 $b$ 色;在靠有的 $n$ 个球中选 $k$ 个染成 $c$ 色,剩余 $n-k$ 个 $d$ 色。

  • 对于 r.h.s.

有 $3n$ 个 $\star$ 色球,钦定其中 $n$ 个,再拿出一个全 $0$ 序列,选出 $n$ 个赋值为 $1$,此时已经为右式的组合意义了,我们考虑把左右式对起来。

拿出两个指针 pq,分别指向为 $3n$ 个 $\star$ 色球中的未钦定球,和 $0/1$ 序列,两指针同步移动。

q 碰到 $1$,把 p 所指的球染成 $b$ 色,当 p 之前有恰好 $n$ 个「钦定或 $b$ 色」球时停下。那么此时设 p 前面有 $k$ 个钦定球,$n-k$ 个 $b$ 色球,p 后面有 $o$ 个球,那么 q 后面还有 $o+k$ 个数,其中恰好有 $k$ 个 $1$。

p 后面的球放在 q 之后 $0$ 的位置上,把 $1$ 的位置染成 $d$ 色,把 p 前的球和这个拼起来就和 l.h.s. 对上了。


呃呃呃,组合恒等式法。

combinatorics

「ceoi 2009」harbingers
上一篇 «
费用流去掉负权边
» 下一篇