「Luogu-T47720」孤立元

传送门

自己出的第一道毒瘤数论题。

对于每一个 $i(1<i<n)$，如果它成为了孤立元，那么一定有 $i-1\notin B$ 且 $i+1\notin B$，而其他 $n-3$ 个数无论怎样都无法阻止 $i$ 对所有孤立元的和产生贡献，此时，其他 $n-3$ 个数中有且仅有 $m-1$ 个属于 $B$，其总方案数为 $C_{n-3}^{m-1}$。而对于 $1$ 和 $n$ 来说，它们只有 $1$ 个相邻的元素，因此方案数为 $C_{n-2}^{m-1}$。本题答案即为

$$\frac{\sum_{i=2}^{n-1}iC_{n-3}^{m-1}+(n+1)C_{n-2}^{m-1}}{C_{n}^{m}}$$

将这个式子进行一系列惨无人道的化简与整理后，我们得到如下形式

$$\frac{m(n+1)(n-m)(n-m-1)}{2n(n-1)}+\frac{m(n+1)(n-m)}{n(n-1)}$$

Updated on 2018-10-10

之前公式写错了，分子上的 $m$ 全都漏掉了（

以及，我们还可以将上式继续整理：

$$\frac{m(n+1)(n-m)(n-m+1)}{2n(n-1)}$$

以及，顺便测试了一下新的快读板子，然后发现 #ifdef 真没用也可能是我太菜了（

Updated on 2018-10-16

好吧我当时并不会用 #ifdef（

以及，标程经过一系列丧心病狂的卡常卡到了 $1861\text{ms}$，最慢的一个点只跑了 $300\text{ms}$ 不到。截至本日，另外两个切掉这道题的 $\text{dalao}$ 最慢的一个点也只跑了 $400\text{ms}$ 上下。我要不要考虑加强一波数据或者缩一波时限呢？所以说为什么我当初在本地测的时候平均每个点 $500\text{ms}$，是我们机房的电脑太菜了吗（

于是做法就有了，先 $O(n)$ 预处理一遍，然后单次询问即可 $O(1)$ 解决。

但是常数好像会很大，我原计划是要将数据范围开到 $10^{7}$ 级别的，然而自己写的标程都跑不过，于是只能一路削到现在的 $10^{6}$……