AGC065D Not Intersect 题解

· · 题解

@RedreamMer 题解重制版。再次拜谢 ZAK 的做法。

 

Raney 引理

对于整数序列 a_0,\dots,a_{n-1}，如果 \sum a=1，那么 a 的 n 个循环移位的序列中恰好有一个满足：该序列的所有前缀和均为正整数。

证明：构造周期为 n，定义域为 \Z 的函数 f(x)，满足 f(x)=f(x-1)+a_{(x-1)\bmod n}。

偷了张图，这是序列 a=\set{1,3,-4,1} 构造出的函数。

用直线 y=\frac xn+b 从 b=-\infin 处往上平移去切函数图像。图中切线为 DH。

此切线与 f(x) 在一个周期中恰好切于一个整点。

这里认为周期是 [x,x+T)。容易说明切点是整点。设切点为 (x_0,y_0)。因为直线的斜率为 \frac1n，所以直线 y=\frac xn+b 除了在 x_0 处，在该周期内的其它函数值均不为整数，不可能与 f(x) 相切。

从 x_0 开始的循环移位就是我们要求的：序列的所有前缀和均为正整数的那个循环移位。

还要说明其它循环移位的序列均存在某个前缀和不是正整数。容易说明其它循环移位的序列在 x_0 之前的前缀和 \le0。

引理证毕。

例题：P6672 清华集训 2016 你的生命已如风中残烛

我们还需要用到另一个引理：

对于整数序列 a_0,\dots,a_{n-1}，如果 \sum a=1，那么 a 的 n 个循环移位的序列均不相同。

对于 n=1 显然成立。对于 n>1，考虑反证法。如果有两个循环移位的序列相同，那么存在周期 T<n，使得 a_i=a_{(i+T)\bmod n}。

从 i 开始在模 n 意义下不停以步长为 T 的步跳，跳到的点均和 a_i 相等。容易说明等价类大小为 \frac n{\gcd(T,n)}，可以进一步得到 \frac n{\gcd(T,n)}\mid\sum a。

在 n>1 时，\frac n{\gcd(T,n)} 也大于 1。\sum a=1 需要是某个大于 1 的数的倍数，假设不成立。

引理证毕。

 

构造双射

以下的讨论均对于 n\ge3。

把圆看成一个正 n 边形。加的 m 条边相当于在对正 n 边形进行划分。

正 n 边形上相邻的两点之间的边是否连接不会对划分的形态产生影响，不妨枚举有多少条这样的边。设有 i 条，方案数为 \binom ni。现在问题变成了要连接 m-i 条边，连接的边不能与原来正 n 边形上的边重合，问可以得到多少本质不同的正 n 边形划分。

破环为链。容易发现限制不会产生变化。

构造双射。假设有个栈，初始为空。我们要把 j:2\to n 依次加入栈中。在任意时刻可以选择：

如图，这样的图形可以用以下的流程描述。

操作 栈
加入 j=2 \set{2}
加入 j=3 \set{2,3}
加入 j=4 \set{2,3,4}
取 k=1，连边 4\to2 \set{2,4}
取 k=1，连边 4\to1 \set{4}
加入 j=5 \set{4,5}
加入 j=6 \set{4,5,6}
加入 j=7 \set{4,5,6,7}
加入 j=8 \set{4,5,6,7,8}
取 k=2，连边 8\to5 \set{4,5,8}

主播主播，有没有更加深刻的理解？有的，当然有的。

栈中的数和 1 就是当前所有可以连边的点。每次连边的时候可供连边的点都会减少。这同时保证了不会连出相邻的边。

这个过程其实就是扫描边的右端点 j。把所有右端点为 j 的边按左端点从右往左的顺序加入。

其实这样会存在一个问题。就是边 n\to1。这条边属于相邻的边，其实是不应该存在的。但是在上面的过程中，只要把最后一步改成 k=4，就会连出这样的边。

解决的方式是我们钦定必须有边 n\to1（但这条边实际上不存在）。这样做的好处在于：

 

计算答案

特判掉 n\le2。对于 n\ge3，套用 Raney 引理计算答案。

假设我们有一个操作序列：序列中有 n-1 个 +1，m-i+1 个负数，这些数的和为 1。但是这个序列可能是不合法的。序列合法的条件是：栈中任意时刻都要有至少一个数，即序列的所有前缀和均为正整数。

根据 Raney 引理，这个序列的循环同构中恰好有一个是合法的。又通过前面的引理可以得到，这个序列所有的循环同构都不相同。这样就不会计重了！

容易发现根据当前的计算方式，可以得到 m-i+1\le n-2。因为 i\le n，所以只有 m\le2n-3 时答案才不为 0。

令 k=m-i+1。只要统计合法操作序列数量即可，每个合法操作序列对答案的贡献是 \frac1{n-1+k}。有 m-i+1 个负数，这些数的和为 2-n。先给每个数分配 -1，还剩 n-2-k 个负单位可以分配。插个板得到 \binom{n-2-1}{k-1}。然后要把 n-1 个 +1 和 k 个负数归并在一起。方案数为 \binom{n-1+k}k。

总答案：

\sum_{i=0}^{\min(n,m)}\frac 1{n-1+k}\binom ni\binom{n-3}{k-1}\binom{n-1+k}k

时间复杂度 O(n)。代码。