发挥一般
很趣味的题，考虑计算答案的过程，首先从某个点开始，遇到
平衡树模板，不做评价，权当练习使用 pb_ds。
其实有平衡树之外的多种解法。
对这个东西其实一直不熟悉，如果序列分块不容易解决或者复杂度多一个 \(\log\)，那么考虑对值域分块，记录和每块数值有关的信息。
\(O(1)\) 改可以只改对应数值块和自身的数据，\(O(1)\) 查可以对块和块内维护前缀信息或者其它预处理信息。
写过若干次，但不熟练。
以前缀和树状数组为例，它每个节点 \(x\) 维护的信息是 \((x-lowbit(x),x]\) 区间的全部信息。
更新时一直 +lowbit，保证了恰好能够维护这些信息。
所以如何二分也比较明晰了。
1 | int now=0,sum=0; |
有些价值的题，"优化状压DP" 还是有一些话题可谈。
李超树模板题，类似 CDQ
分治的思路或者平衡树维护凸包其实很趣味，但是没有什么启发意义。
等有时间了写一份斜率优化的总结。
假的可持久化题，弄到树上做撤销就行。
其实写可持久化 FHQ-Treap 更容易
参考 关于平衡树
还可以用块状链表搞定。
树套树模板题，但是有一些不同的思考方式。
我采用了线段树套值域线段树，但是需要同时二分多个主席树，不够优雅。
一般来说，位置树套值域树更加常见，但如果有些涉及到二分的操作，也许把它们反过来会更加容易，因为反过来之后就可以在数据结构上二分，减少一个 \(\log\)。
其实位置树套值域树也可以在数据结构上二分，只是实现起来相对麻烦一些。
可以采用值域线段树套平衡树。
这个时候 FHQ-Treap 的优势就体现出来了，很简单的可以查到 \([l,r]\) 区间内数的个数。
带修莫队可以处理单点改区间查的问题，修改一共 \(O(n^{\frac{5}{3}})\) 次，查询 \(O(n)\) 次，使用 \(O(\sqrt n)-O(1)\) 的值域分块即可处理问题。
给你一棵有根树，定义一个点合法当且仅当它到根上的点全为黑色，否则不合法。
最开始所有点为白色，每次选一个不合法的点涂黑，每个点可以被涂黑多次。
问所有点被涂黑的期望次数
这次想题引爆了某人概率论基础不扎实的炸弹。
考虑每个点被涂黑的顺序，是一个排列，取到每种排列的概率相同。
考虑使用全期望公式计算，先考虑固定一个排列时的答案。
先假设只有 \(3\) 个点，且顺序为 \(3,2,1\)，也就是赠券收集问题。
选第一个点的期望次数为 \(1\)，因为所有满足这个排列的样本点都是以 \(3\) 开头，选第二个点，期望次数是多少，或者说，选出第一个点后，下一个被选择的点，在顺序为 \(3,2,1\) 的前提下，是 \(2\) 的概率是多少？
选第二个点时，可以选的点有 \(3,2\)，选择每个点的概率相同，所以概率为 \(\frac{1}{2}\)
虽然原本每个点概率时相同的，但是我们求的时条件概率，条件概率的样本空间已经被改变了，所以选择每个点的概率不再相同。
考虑概率的定义，\(P=\frac{事件大小}{样本空间大小}\)，考虑该条件的集合和事件与条件的交集，因为此题样本空间无限大，所以考虑将一个无限长序列映射到我们的样本空间，容易发现这样的映射不会改变概率函数。
设 \(k\) 为已经选取的数的个数，\(n\) 为数的总数。 $$ \[\begin{align} P=&\lim\limits_{m\rightarrow \infty}\dfrac{n^{m-1}}{\sum\limits_{1\le i\le m} k^{i-1}\times n^{m-i}}\\ =&\dfrac{n^{m-1}}{\frac{n^{m}}{n-k}}\\ =&\frac{n-k}{n} \end{align}\] $$ 这是在正确的样本空间算出的正确结果。
从 Beyes 公式考虑： \[ \begin{align} P(下一个值为目标|满足排列限制)=&\dfrac{P(下一个值为目标\wedge满足排列限制)}{P(满足排列限制)}\\ =&\dfrac{\frac{1}{n}\times\frac{1}{(n-k-1)!}}{\frac{1}{(n-k)!}}\\ =&\dfrac{n-k}{n} \end{align} \] 神奇吧？
贝叶斯公式连接了条件概率和原问题的样本空间。
样本空间无限大的时候要小心，不能轻易认为两个元素等价，因为此时 \(\infty \ne \infty\)。
用贝叶斯公式好好算算吧。
草率的断言概率为 \(\frac{1}{2}\)，很大一部分原因都是认为两个正无穷时相等的。
有了这个东西就可以愉快的推狮子 NTT 了。
其实这种题还有一种更加普遍的做法，期望线性性，考虑每个点被选的次数，相加可以得到最终答案。
期望线性性来源于期望的定义，一个随机变量是一个函数，定义域为样本空间，值域为 \(\R\)，随机变量的期望为其密度函数积分的收敛值。
因此，无论两个随机变量是否独立，它们的期望都是可加的。
感性理解的话，两个随机变量之和的期望等于这样一个随机变量的期望：每个样本点的取值为两个随机变量在该样本点的取值之和，期望可以粗略理解为随机变量在样本空间每个点的平均值，因此随机变量的期望可加。
所以可以考虑每个点被选的期望次数，如果选到了不在这个点到根路径上的点，那么我们忽略这一次选择，这样的忽略不会影响这个点被选的期望次数，然后问题变成了一条链上的最后一个点被选择的期望次数。
注意，我们只关心这个点被选择的期望次数。
考虑怎么求这玩意，因为整个过程在点到根路径上所有点被选择之后才会结束，所以像赠券收集问题一样倒序。假设有 \(k\) 个点还没选，总共 \(n\) 个点，其中 \(w\) 个点可以选，那么转移答案是 \(dp[k]=\frac{k}{w}dp[k+1]+\frac{w-k}{w}dp[k]+\frac{1}{w}\)
移项得到 \(dp[k]=dp[k+1]+\frac{1}{k}\)，实际上和 \(w\) 无关，所以就很好算了。
官方题解的说法是如果考虑可以选已经 good
的点，最终答案不变，我理解不了这个过程。
upd：其实现在也可以理解了，因为如果选了已经 good 的点，那么再选一次就行了。
有几个比较重要的地方，一是忽略和答案绝对无关的操作，二是考虑计算过程。
以下概率均为古典概率模型，暂时不讨论几何概型。
这两个东西是我自己定义的，算概率之前，必须搞清楚事件和条件的区别，下面提两个搞不清楚事件和条件导致的问题。
有三个门，一个门后面有汽车，另外两个门后面是山羊。
你可以先选择一个门，之后主持人打开一个门，门后是山羊
问此时两个门后有汽车的概率是多少
每个门后有山羊的概率是相等的，打开一个门不会影响另外两个门的状态，故另外两个门后有山羊的概率是相等的，故答案为 \(50\%\)
另外两个门有山羊的概率是 \(\frac{2}{3}\)，排除一个选项，所以选择的门后有山羊的概率是 \(\frac{1}{3}\)，另一个门的概率为 \(\frac{2}{3}\)。
有个酒鬼，每天各有 \(30\%\) 的概率去 \(A,B,C\) 三个酒吧，还有 \(10\%\) 的概率呆在家。
一个警察要找他，警察已经找了 \(A,B\) 酒吧，都没找到他，问在 \(C\) 酒吧找到酒鬼的概率。
在酒吧的概率是 \(90\%\)，\(A,B\) 都没找到，说明一定在 \(C\)，所以在 \(C\) 找到酒鬼的概率是 \(90\%\)。
这个思路和上一个问题思考方式二类似，但是是错误的，因此说它不严谨。
已知不在 \(A,B\) 酒吧，那么在 \(C\) 酒吧和在家的概率之比是 \(3:1\)，因此答案为 \(75\%\)。
这种方式的问题在哪里不必多说了。
思考这个问题前应该回到概率定义的几个要素：样本空间，样本点，事件。
一个事件的概率被定义为事件大小除以样本空间大小。
第一个问题中，样本空间的大小为 \(3\)，需要计算在某个不被选择的门后面是羊的情况下，选择的门后面是车的概率。
事件的大小为 \(1\)，因此概率为 \(\frac{1}{3}\)，另一个不被选择的门后面有车，其事件大小为 \(2\)，因为最初样本空间中在两个门后的样本点都属于该事件（如果是这两个事件之一，那么没被打开的另一扇门后必定是车）。
推广到 \(n\) 门问题，主持人随机打开一个未被选择且没有车的门，那么样本空间大小为 \(1\)，不改变选择的事件大小为 \(n-2\)，改变选择的事件大小为 \(n\)。
通常解决一个概率问题需要明确事件域，即我们关心的所有事件，如果事件域不合法，那么
假设选的门是 \(1\) 号，已知 \(2\) 号门没有车，那么 \(3\) 号门有车的概率是 $$
我们需要明确问题中这个概率定义是在哪个样本空间下的，问题中样本空间的大小很明显是 \(3\)，而在被开的门后是山羊的事件大小为 \(2\)
|
|
|
/
/
F1: xxxx oooo
…………
常用算法有 Kruscal 和 Prime，以下会谈一些 MST 的性质和两种算法的证明
核心思路是证明任意时刻边集均为一颗 MST 的子集。
归纳的，令当前边集 \(F\) 属于的 MST 为 \(T\)，考虑新加入的一条边 \(e\)，如果 \(e\in T\)，自然成立。
如果 \(e\notin T\)，那么 \(e+T\) 构成了一个环，考虑该环上所有边 \(E_i\)，一定满足 \(w_{E_i} \le w_e\)，否则 \(e\) 应该在 \(T\) 中，得到更优的 MST，所以 \(E_i\) 已经在 \(e\) 之前被加入，构成了一条完整的链。
所以不会加入 \(e\)，进行下一步。
给你一张图，问任选 \(i\) 条边，使得图联通的方案数有多少种。
记录联通性动态规划
考虑 \(dp[mask][i]\) 表示子图 \(mask\) 的答案，转移时发现重复了，因为两种不同的子图分配方案最后可能对应到同一种选边方式，所以我们需要一个顺序一类的东西来保证不重复。
一种比较可行的方式是计算记录顺序的情况下的方案，这样可以钦定枚举的两个子图一定是最后连上的，最后除以一个阶乘。
另一种方式是直接容斥，考虑计算选 \(k\) 条边后不联通的答案，枚举得到的两个连通块就是断开的，还是有重复的问题，但是我们可以钦定每种图只会在与 \(1\) 相连的连通块处被统计，这是经典的连通图计数方式。
成功垫底
难 T
度 1
倒 磕
序 了
自 一
闭 万
场 年
我不会的题。
求有向图可达点数量实际上不存在低于 \(O(n^2)\) 的算法，所以得考虑给定图的性质。
显然给定的图是个平面图。
然后定义一个东边的点是有效的，当且仅当它能到一个西边的点，一遍 \(BFS\) 可以把有效点找出来。
然后对于所有点，它能到达的有效点集合一定是一段区间，考虑反证，对于某个点，如果被夹在中间的一个有效点到不了，那么如果其它点可以到就只能穿过一些边，这是不可能的。
写拓扑排序是非常傻逼的行为，直接对每个有效点拓展，算出西边每个点到达有效点坐标的最值就行。
会但是考场写不出来的题。
考虑枚举排列计算 MST，本质上需要求前 \(i\) 个边能将图联通的排列一共有多少个。
可以考虑计算出任选 \(i\) 条边后图联通的选法有多少种，然后通过容斥计算出恰 \(i\) 个边联通的排列个数。
可以记录联通性动态规划搞定。
复杂度 \(O(bell(n)\times m^2)\)
枚举联通往往可以弄成二进制枚举联通状态，逆序考虑联通块的构成方式，发现求任 \(i\) 条边联通的方案数，转移的时候是不强调顺序的，所以枚举子集会导致重复，不妨直接考虑顺序，计算原问题的答案。
设 \(dp[mask][i]\) 表示只考虑 \(mask\) 子图，答案为 \(i\) 的排列个数，转移就可以枚举子集，从上一条边的状态转移，需要进行一些排列组合，复杂度 \(3^n\times m^4\)。
高达 \(m^4\) 的多项式复杂度还是太逊了，考虑继续优化。
其实我们很想直接任选 \(k\) 条边，然后排除掉不合法的情况，这样能够求出答案至多为 \(k\) 的个数，容斥之后就没有问题了。
所以考虑如何排除不合法的情况，就是边选好了但是图没联通，这个时候我们就可以枚举一个小连通块，可以用若干边连接内部，若干外部边任选，就是一类不合法的情况，但是这样会算重，我们可以钦定枚举的联通块和 \(1\) 联通。
复杂度 \(O(3^n\times m^2)\)。
这一类图论上的二进制枚举问题，往往可以先从枚举联通块入手，再考虑子图的答案，最后综合运用容斥等计数手段，得到复杂度优秀的做法。
非常有意思的题
考场上的想法，主要受到某道题的启发。
只考虑最大值，\(O(n)\) 可以扫一遍，单调栈维护当前每一段的最大值与和。
很浪费，因为我们本质上对每个右端点都求了合法左端点区间的答案，考虑能不能复用右端点的答案。
其中一种方式是分块，考虑一段右端点到每个左端点的答案的前缀和，然后查询就可以被拆分了。
为什么我们会分块，回到那道题，我们有办法通过一些预处理结果得到两个区间并的答案，但是无法快速合并两个预处理结果，所以我们分块，只需要预处理一次。
但是利用随机数的性质我们发现其实可以快速合并预处理的结果。
将问题转化为两种基本形式，相离和重合，这是容易的。
先考虑相离怎么做
考虑利用随机的性质，发现任意一段区间，其有效的贡献个数为 \(\ln\) 个，即从区间首或位开始的最长连续上升序列，然后枚举两个 \(\ln\) 的区间合并，搞定相离的情况，视实现是 \(\ln^2\) 或者 \(\ln\)，后者常数较大可能并不优秀。
然后是重合，能不能合并两个重合的区间得到新的区间，可以！转化为一个相离和两个更小的重合问题，因为数量是 \(\ln\) 的，所以合并预处理信息是可能的。
但是，为啥要用线段树，因为没有逆元！但是这道题是可以将一个大重合问题减去一个相离和一个小重合问题得到另一个小重合问题的，所以对大重合问题做前缀和即可。
对于二维统计问题，常常可以考虑固定预处理其中一维，尝试快速通过预处理结果查询第二维。
这道题中，我们可以预处理每个点作为第二个区间中的点时，在第一个区间中每个点的答案。但实际上这个数据量是 \(O(n)\) 的，没有办法快速搞定，那不妨考虑只处理其前缀和与后缀和，看看是否能够压缩信息。
考虑单个右端点对一段区间查询，考虑区间最大值，如果落在自身或者空区间，那么答案容易计算，如果落在左区间
考虑它前面第一个比它大的位置，如果不存在或者在空区间，那么答案可以通过前缀和快速计算
考虑区间相离的基本情况。由于单点我们都没有办法做，所以不太能直接搞，但是容易发现区间重合时可以搞定的，考虑区间最大值的位置，跨过它的答案容易统计，不跨过它，我们处理了每个点为右端点和左端点时答案的前缀和，那么由于不跨过最大值时，在最大值另一侧的答案完全不受同侧的影响，所以前后缀和减去最大值所在位置的前后缀和就可以得到重合的答案。
有了重合，我们可以解决区间相邻的答案，定义求两个区间答案的运算是 \(\oplus\)，那么对于两个相邻区间有\((a+b)\oplus(a+b)=a\oplus a+b\oplus b+a\oplus b\)。
我们能搞定的是 \(a\oplus a\)，对于相离的区间，转化为相邻区间做 \(a\oplus c = (a+b+c)\oplus (a+b+c)-a\oplus a-b \oplus b-c\oplus c - a\oplus b -b\oplus c\)。
因而搞定了所有情况。
如果直接这么写，写出来很丑，实际上由更优雅的写法，考虑差分区间，如果左端点大于右端点那么没有问题，\([l_1,r_2]\) 全部统计，那么会有重复 \([l_1,l_2-1]\) 这一段区间就是被重复统计的，当然这个区间可以不存在，需要减去，然后再减去 \([r_1+1,r_2]\) 这段有可能不存在的区间的答案，最后加上可能被算重的 \([r_1+1,l_2-1]\) 区间。
反正这个思想挺神的，看上去有问题但确实是对的，比直接写优雅很多。
考虑每个数对答案的贡献，弄出左右两边第一个比它大的数，那么这些区间以内跨过它的，都在它的贡献范围内，左右端点可以弄成 \(x,y\) 坐标，这是一个矩阵加。
考虑查询，本质上也是在查询 \(x,y\) 坐标各在一段区间内的答案。
于是就是一个修改全部在查询前面的矩阵加矩阵查问题，可以用树状数组解决。
说着轻松，但其实还没写过这种东西，简单思考下怎么做。
首先区间查被差分成 \(\ge x,\ge y\) 的区域加一，区间查变成 \(\le x,\le y\) 的区域查询，还是回到了二维偏序问题。
点是 \((x_1,y_1),(x_2,y_2)\)，条件是 \(x_2\ge x_1\wedge y_2\ge y_1\)，贡献是 \((x_2-x_1)\times(y_2-y_1)\)，是不是很阴间？所以多维护点东西，一个 \(cnt\) 树状数组搞定 \(x_2\times y_2\)，两个分别加 \(x,y\) 来搞定 \(x_2\times y_1,x_1\times y_2\) ，再来一个统计 \(xy\) 搞定剩下那一项，其实还算好写。
考虑刻画出图的形态，它是一个基环内向树森林。
容易发现只用将 \(1\) 和其它点连边，然后有些点是必须连的，入度为 \(0\) 的，编号非 \(1\) 的点必须连。
先不考虑环，这样连了之后，又有一些点是必连的，而且容易发现连这些点一定最优，所以继续连。
连到不是环上的所有点都连上为止。
现在还剩一些环，环上一些点是合法的，需要用长度为 \(k-1\) 的线段取覆盖环，让所有点合法。
容易发现确定某个起点之后就能贪心了，考虑连续的 \(k+1\) 个不合法点，枚举每一个并确定最少数量，然后取 \(\min\) 就行，因为这连续的 \(k+1\) 个不合法点一定有一个是起点。
挺套路的题，通过 00 11 得到 \(1,0\) 的个数，容易发现 10 01
的总个数已经被确定且容易构造。
但是有边界，考虑 00 11 个数为 \(0\)，此时可以取 \(1\) 个也可以取 \(0\) 个。然后 100->55
这种两个构成的计数问题，一定要考虑只有一个的边界情况，
注意我们通过题目信息得到新信息的过程，要看看是否为一一映射。
有趣的题。
我先思考了如果一个问题我限定一个时间 \(T\)，等 \(T\) 秒过完，得到的收益，实际上我们可能有根据当前信息改变等待的这个时间，所以这样不行。
接着考虑 \(t\) 时刻到 Trie 上 \(j\) 点的最优方案，发现其实不好转移。
注意到我们能决定的只有回答还是等待，所以这样的话转移会带上一个概率，但是这个概率却是无法相加后取最值的。
正难则反，考虑到 \(j\) 点时还剩时间 \(t\)，最优能得到什么，这样的话，转移就只和我们的决定有关，成功解决这道题。
等价于求最优解并构造方案。
它的修改本质上是需要决定一个最值，付出对应的代价，然后如果某个数绝对值严格小于最值，那么这个数的正负性就可以被指定，然后指定最值后最优化代价就是要求出删去的数的最小个数。
我们需要求出对于每个最值的删除数最小个数。
由于不让 \(0\) 出现，所以先判掉不修改只删除的方案，这个是简单的。
有两种思考方式，对应了两种求答案的方式。
一个数为负视为 -1，为正视为 1，可调整视为
0
考虑一段极长连续相同子段，如果不为
0，那么必须删去然后只剩下一个。
如果为
0，其左右两边的状态和自身长度决定了它应该被删去一个或者不做任何处理。
如果能够维护机场连续相同子段，就可以得到答案。
考虑最值从小到大变化的过程，每次会把一个非 0 数改为
0，经典的 set 维护线段问题。
考虑动态规划。
设 \(dp[i][0/1]\) 表示考虑到第 \(i\) 个数，末尾为 \(-1/1\) 的代价。
\[ v_i=0:dp[i][o]=\min(dp[i-1][o\oplus 1],dp[i-1][o]+1)\\ \]
\[ v_i\ne0: \begin{cases} dp[i][v_i]&=\min(dp[i-1][v_i\oplus 1],dp[i-1][v_i]+1)\\ dp[i][v_i\oplus1]&=dp[i-1][v_i\oplus 1]+1\\ \end{cases} \]
然后就是动态 DP，考虑能不能写成矩阵乘法的形式，发现是一个 \(+\min\) 矩阵乘法。
线段树维护即可。
写一下学计算几何的感悟。
\(\mathbf{a} \cdot \mathbf{b} = |\mathbf{a}|\times|\mathbf{b}| \times \cos\theta = x_1x_2+y_1y_2\)
常用来计算向量夹角。
\(\mathbf{a} \times \mathbf{b} = |\mathbf{a}|\times |\mathbf{b}|\times \sin\theta = x_1y_2-x_2y_1\)
几何意义是两个向量围成的平行四边形的面积。
从 \(\mathbf{a}\) 旋转到 \(\mathbf{b}\)，如果角度小于 \(\pi\)，那么为正，否则为负。
证明的话，方向是直接定义的，先不管，尝试证明。 \[
(x_1y_2-x_2y_1)^2=\sin^2\theta \mathbf{a}^2\mathbf{b}^2\\
\] 我觉得这个不太适合用 markdown 写下来。
为什么方向是对的，可以替换一下 \(x,y\) 变成 \(\sin,\cos\)，然后很自然是对的。
可以用来求线段交点。
算一下 \(BCD,ACD\) 的面积，用相似求 \(AO\)，就可以得到 \(O\) 点坐标。
有人不会用这个东西，我不说是谁。
\(\mathbf{a}\) 转 \(\alpha\) 角：\((|\mathbf{a}|\cos(\theta+\alpha),|\mathbf{a}|\sin(\theta+\alpha))\)。
和差角公式记不住的话朱某要来找麻烦，所以有人还是能记住。
\(S=\dfrac{\sum\mathbf{a_i}\times \mathbf{a_{(i+1)\%n}}}{2}\)
盗一波图。
按照逆时针方向看，多边形凸包永远往左拐。
可以用一个点 \(P\) 加方向向量 \(\mathbf{v}\) 存储，也可以顺便记一个 \(P_2\)。
求 \(PQ\times \mathbf{v}\) 即可，为正在下方，为负在上方，\(0\) 则在线上，前提条件是向量 \(\mathbf{v}\) 的 \(x\) 为正 。
两个矩阵不交，则通过快速排斥实验。
比较简易的方式是对于两维独立判断线段是否有交，如果任何一维无交，则通过快速排斥实验。
跨立实验则是判断一条线段的两端是否在另一条线段的两边，可以用向量叉乘做。
相互做跨立实验，如果均能通过，则线段有交或共线，结合快速排斥实验可以判断线段是否有交。
两条线段共线但不交也能通过跨立实验。
先判断平行和重合。
然后对于两条直线 \((P_1,\mathbf{a_1}),(P_2,\mathbf{a_2})\)，设 \(Q=k\mathbf{a_1}+P_1\)，则有 \((P_2-(k\mathbf{a_1}+P_1))\times \mathbf{a_2}=0\)
叉积有分配律，所以直接拆开解 \(k\) 然后带回去。
\(k=\dfrac{(P_2-P_1)\times \mathbf{a_2}}{\mathbf{a_1}\times\mathbf{a_2}}\)
如果你敢约分，朱某就敢把你鲨了。
算出 \(PQ\) 在 \(\mathbf{v}\) 上投影的长度和方向（点积），\(P\) 加上这个就行。
可以先算垂足，也可以用记下来的另一个点带面积公式算。
模长相同的方向向量相加，得到角平分线的方向向量，证明考虑构造菱形。
于是乎求凸包的时候多了一种判定方式：
如果是上凸包，弹出点的充要条件是上个点在该点与上上个点的连线下方
下凸包，弹出条件就是在上方，比斜率好一点，而且判共线很方便。
求出点到直线距离和垂足，然后勾股定理算两个点。
半径相等可以求中点勾股定理偷懒，半径不等可以选一个三角形解三角形。
具体的，可以算出一个角的 \(\cos\) 然后旋转向量，最后乘半径再加上去。
勾股定理，旋转，解三角形。
有人几何学的很差，考场上还非要写。
exchange-argument，已经是咱非常了解的题目啦啦啦。
套路题，二分然后最短路
对这种题还是比较熟悉了，不好处理的区间问题分类讨论变偏序，二维偏序解决区间交，贡献独立的情况，李超树搞定贡献分离的情况。
当然可以 CDQ 然后凸包上二分，但是我觉得我更擅长一般的数据结构。
我.... 不会解析几何。/ll /ll。
办法其实非常蠢，一条可行的最短路一定经过圆弧交点，且只会在这些交点拐弯。
所以求出所有交点，然后判断交点两两路径是否合法，连边跑最短路。
可行的交点其实不多，得判掉在圆内的点，然后剩下点的个数感觉上是 \(O(n)\) 的，实际也是 \(O(n)\) 的，证明我不会，等问数学竞赛的回来再补。
然后判合法本质上是判一条路径是否被覆盖，需要写线圆交，然后前面要写圆圆交，这玩意不是一次函数，会非常裂开，我写的很丑。
圆圆交直径相同，比较好办，用极坐标可以偷懒，线圆交相当折磨。
见 计算几何入门。
用向量写会相当舒适。
经典的 01 分数规划问题，二分小数，直接 DP
，然后记录转移状态，倒推分数得到答案。
注意这种答案可能为 0 的 01 分数规划一定要从 -1
开始二分答案，不然可能会取不到 0。
注意到其实它的分子分母都比较小，二分分数也是可行的一种方式 。
考场上的错误其实挺离谱的，就不细说了。
二分分数不用倒推，就很简单了。
套路题。
观察发现如果每张牌个数都大于等于 \(2\)，那么一定合法。否则一定会用一些顺子来凑，同一个位置最多被三个顺子用，所以如果一个位置超过 \(5\) 个，可以视为 \(5\) 个，状压 \(DP\) 出合法的状态，对每种状态计算答案并求和。
拿到状态后计算答案就是个组合数。