cf1550D excellent arrays

题意

Link

---

题解

首先我们观察如果 \(a_i+a_j=i+j\),那么 \(a_i-i=-(a_j-j)\)。

那么我么定义一个属性值 \(v_i=a_i-i\)。

那么 \(v_i\in\{d,-d\}\),肯定是最优的。

问题转化为我们选 \(\lfloor{\dfrac{n}{2}}\rfloor\) 个 \(d\)，选 \(\lceil{\dfrac{n}{2}}\rceil\) 个 \(-d\) 作为 \(v_i\)。

然后 \(l\leq a_i=i+v_i\leq r\)。

然后我们肯定可以确定出最小的的可以 \(-d\) 的，记作 \(a\)；最大的可以 \(+d\) 的，记作 \(b\)。

接下来我找到了两种方法。

1. 这个是我翻\(\color{black}j\color{red}iangly\)的代码，得出的答案。

   我们直接枚举 \(d\in[1,\infty]\),然后确定出 \(a,b\) 的区间范围。

   \(a=l+d,b=r-d\)。

   然后我们可以确定出 \(i\in[1,a)\) 必须要 \(+d\) , \(i\in(b,n]\)，必须要 \(-d\)。

   然后可以选的区间为 \([a,b]\) ，然后需要 \(\lfloor\frac{n}{2}\rfloor\),\(\lceil\frac{n}{2}\rceil\) \(-a\) 个 \(+d\) 的。

   考虑这个 \(d\)​ 枚举状态高达 \(2\times 10^9\)​ ,\(\mathcal{\color{gold}TLE}\)​。

   发现当 \(d\in[1,\min(1-l,r-n)]\) 时，可以取满 \(\binom{n}{n/2}\)。

   然后就剩 \(d\in(\min(1-l,r-n),\min(1-l,r-n)+n]\)。

   显然复杂度为 \(\mathcal{O(n)}\)

2. 这个是我的做法

   我们可以枚举 \(a,b\),即上文提到的 \(a,b\)。

   现在我们可以反向确定 \(d\)。

   \(d\in[1,\min(a-l,r-b)\)]。

   \[ans\leftarrow \binom{b-a-1}{\lfloor\frac{n}{2}\rfloor-a}\]​​

   也就是枚举 \(a,b\)​。

   \[ ans=\sum_{a=1}^{n}\sum_{b=a+1}^{n}\min(a-l,r-b)\binom{b-a-1}{\lfloor\frac{n}{2}\rfloor-a} \]

   拆 \(\min\)​,直接看后面。 \[ ans=\sum_{a}\sum_{b}(a-l)\binom{b-a-1}{\lfloor\frac{n}{2}\rfloor-a}+\sum_{a}\sum_{b}(r-b)\binom{b-a-1}{\lfloor\frac{n}{2}\rfloor-a} \] \(a,b\) 范围不写了，没什么必要了。

   现在只需要我们能快速求出 \(\sum_{i}\binom{i}{n}\) 和 \(\sum_{i}i\binom{i}{n}\) 即可。

   \(\sum_{i}\binom{i}{n}\) 是个经典问题。

   \(\sum_{i}i\binom{i}{n}\) 等价于求 \(\sum_{i}(i+1)\binom{i}{n}=\sum_{i}\frac{1}{n+1}\binom{i+1}{n+1}=\frac{1}{n+1}\sum_{i}\binom{i+1}{n+1}\)​。​​也是经典问题。

   done.

   code