Raney引理

一个非常有趣的结论：

$Raney$ 引理：

给你一个数列 $\\{a_i\\} (1 \le i \le n)$ ，而且定义 $S_i=\sum _{i=1}^n a_i$ ，并且 $S_n=1$ ，求证 $\\{a_i\\}$ 的循环排列里面有且仅有一个序列，满足 $\forall i \in [1,n],S_i > 0$ 。

循环排列的意思也非常好理解。

举一个例子： $a=\\{1,4,-5,3,-2,0\\}$

循环排列为：

显然对于这组数据来说， $4$ 是满足条件的。

如何证明？

看到这类环上的问题，首先考虑拆环成链。

考虑一个无限的数列 $b=\\{a_1,a_2,a_3,...a_n,a_1,a_2,a_3,...a_n,a_1,a_2...\\}$

对于这个数列，再做一次前缀和，设 $f_x=\sum _{i=1}^x a[i]$

注意到 $f_{x+n}-f_x=f_n=1$ ，所以这个函数每过 $n$ 格就会整体向上平移一格：

可以看图理解。

于是我们可以构造斜率为 $\frac{\dfrac$ 的两条直线"夹住"原函数。

可以发现每过 $n$ 个点，下面那条直线就会和函数相切一次。

从那个切点（图中为 $(3,0)$ ）向上走，发现所有的 $S_i$ 都 $>0$ ，因为函数不可能和下面的直线相交。

同时在每 $n$ 个点中，有且仅有一个点和直线相切（因为每过 $n$ 个点函数才会经过一次整点），这就证明了唯一性。

思考， $S_n!=1$ 时，为什么不能说明唯一性？

因为 $S_n!=1$ 时，斜率为 $\fra\dfrac}{n}$ ，不能保证一定只经过一个整点。

比如 $S_n=2,n=6$ 时，就会发现会有矛盾。