AGC020F Arcs on a Circle

一个和值域无关的算法，复杂度 \(O(4^nn^2)\)，不过好像可以用子集卷积和拉格朗日插值优化至 \(O(3^nn^3)\)。

如果说原问题在整数上做，我们通常可以用生成函数来刻画容斥的式子，求个二维 \(\exp\) 状物就可以了，但是在实数域似乎不太好扩展，但实际上是可以扩展的。

原问题实际上可以抽象为类似连通子图计数的东西，因为环计数实际上就是链计数乘上第一段的长度，而要求第一段为连通块，而连通块具有和连通子图相似的性质，求个类似 \(\ln\) (其实并不是 \(\ln\))，就可以了。特别的，如果不存在一个弧跨过 \(C\) 到 \(0\) 这部分时是数不到的，但这部分是平凡的，就是 \(\prod_{i=1}^{n}\frac{C-l_{i}}{C}\)。而能通过我们以如上方式数到的都是不合法的方案，因为合法的方案不存在任何一个断开位置。

现在我们只需要求连通块的 \(\text{GF}\) 点乘上 \(\frac{x}{C}\)，再与原来的相乘即可就行了，但卷积如何刻画呢？由于直接用概率来描述似乎比较奇怪，我们采用几何概型的思想，将其视为求体积，虽然是高维的。

一个平凡的想法是令 \(F_{S}(x)\) 表示 \(S\) 集合的长度为 \(x\) 内选择的体积和，令 \(G_{S}(x)\) 表示 \(S\) 集合的长度为 \(x\) 内选择的并要求构成一个连通块的体积和，那么有 \(G_{S}(x)=F_{S}(x)-\sum_{T\subsetneqq S,T\not=\emptyset} F_{T}(x)*G_{\complement_ST}(x)\)，其中 \(F(x)*G(x)=\int_{0}^{x}F'(y)G(x-y)dy\)(注意其中求导所丢失的常数项要特殊处理)。一开始 \(F_{S}(x)\) 其实是一个分段多项式，因为有要求 \(x\geqslant \max_{i\in S}l_{i}\)，不难发现进行运算后 \(F_{S}(x)\) 的段数最多是 \(2^{|S|}-1\) 的，因为每一个段的界点其实都形如 \(T\subset S,T\not=\emptyset\) 的一个集合 \(T\) 的和 \(W(T)\) (即 \(\sum_{x\in T}l_{x}\))，那么实际上我们可以令 \(F_{S}(x)=\sum_{T\subset S,W(T)\leqslant C}f_{S,T}(\frac{C-W(T)}{C})\)，则 \(f\) 就是一个多项式了。

现在我们只需要能求两个多项式的 \(*\)，就可以求解两个函数的 \(*\) 了，我们要快速计算 \(h=f*g\) 即 \(h(x)=\int_{0}^{x}f'(y)g(x-y)dy\)，如果直接使用暴力二项式定理展开对展开的分别积分可以算出 \(R(a,b)\) 表示 \(x^a\) 与 \(x^b\) 贡献到 \(x^{a+b}\) 的贡献，将 \(R\) 打表之后会发现一个神奇的事情，\(R(x,y)=\frac{1}{\binom{x+y}{x}}\)，这是为什么呢？实际上我们发现我们的 \(*\) 运算其实和第一类欧拉积分非常的相似，而贝塔函数在非负整数部分的取值和组合数倒数有一定关联，对 \(f\) 的导将其变成了一个更加优美的形式:\(\frac{1}{\binom{x+y}{x}}\)。

像定义 \(\text{EGF}\) 一样，我们可以定义一个和积分有关的生成函数 \(\text{IGF}\)，满足 \(f=\sum_{i=0}^{\infty}a_{i}i!x^i\)，这样就可以把多项式的四则运算以及开根求导积分 \(\ln,\exp\) 等东西全部放上去。

现在将 \(G\) 求好了，但如何将其点乘上 \(x\) 本身呢，注意到令 \(H\) 为 \(G\) 的两侧都被覆盖的面积，那么 \(G=\int_{}\int_{}H\)，而我们最终要其实就是 \(\int_{}Hx\)，所以我们求 \(\int_{}G''x\) 即可 (这里一次项需要修正，常数项不用是因为在本题限制下常数项一定为 \(0\))，由于这个算的是第一段，可能还有后面的，令 \(T=\int_{}G''x\)，我们算出 \(T+T*F\) 就是最终的 \(\text{GF}\) 形式了。

由于 \(F\) 只有一段，枚举子集与其中一个子集构成的段的复杂度是 \(O(4^n)\)，暴力卷积是 \(O(n^2)\) 的，所以是 \(O(4^nn^2)\) 的。但似乎子集部分可以子集卷积，拉格朗日插值可以优化掉暴力卷积，于是可以 \(O(3^nn^3)\)，用 \(\text{poly}\) 优化掉子集卷积的暴力卷积可以 \(O(3^nn^2\log n)\)，但是由于 \(n\) 不得不比较小，可能不如暴力卷积。

特别的，该做法在值域非常小的时候可以将段给换成值域，这样里面的枚举子集可以优化掉。另外 \(\text{PKUSC2021 D2T3}\) 招新也可以用同样的方法不带值域，做到暴力卷积 \(O(n^6)\)，三维 \(NTT\) 优化可以 \(O(n^3 \log n)\)，实际上就是把这个东西拼上一个有标号二分图计数的 \(\text{trick}\)。