关于 T507962 加固电视屏幕 的 O(1) 做法

小学知识：

$\LARGE \sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}$

$\LARGE \sum_{i=1}^{n}i=\frac{n(n+1)}{2}$

$\LARGE x(x+1)=x^2+x$

正式推导

已知 $\large ans=C_{3n}^{3}- \sum_{i=n}^{i \geq 2, i-=2} \frac{i(i-1)}{2}$

减号右边可以分成 $n$ 为奇数与 $n$ 为偶数的情况讨论

$\large case 1: n 为奇数$

$\Large \sum_{i=n}^{i \geq 2, i-=2} \frac{i(i-1)}{2}$

$\Large =\sum_{i=2}^{n,i+=2} \frac{i(i+1)}{2}$

$\Large =\frac 1 2 \sum_{i=2}^{n,i+=2} i^2+i$

$\Large =\frac 1 2(\sum_{i=2}^{n,i+=2} i^2+ \sum_{i=2}^{n,i+=2}i)$

$\Large =\frac 1 2 ((4\sum_{i=1}^{\lfloor \frac{n}{2} \rfloor})+\lfloor \frac n 2 \rfloor(n+1))$

$\Large =\frac 1 2 (4·\frac{\lfloor\frac n 2\rfloor\lceil\frac n 2\rceil n}{6}+\lfloor \frac n 2 \rfloor(n+1))$

$\large case 2: n 为偶数$

$\Large \sum_{i=n}^{i \geq 2, i-=2} \frac{i(i-1)}{2}$

$\Large =\sum_{i=1}^{n,i+=2} \frac{i(i+1)}{2}$

$\Large =\frac 1 2(\sum_{i=1}^{n,i+=2} i^2+ \sum_{i=1}^{n,i+=2}i)$

$\Large =\frac 1 2(\sum_{i=1}^{n} i^2- \sum_{i=2}^{n,i+=2} i^2+ \sum_{i=1}^{n,i+=2}i)$

$\Large =\frac 1 2(\frac{n(n+1)(2n+1)}{6}- 4·\frac{\frac n 2(\frac n 2+1)n}{6}+(\frac n 2)^2)$

一些小细节

除法使用逆元

const int inv2 = ...
const int inv6 = ...

x / 2 ==> x * inv2
x / 6 ==> x * inv6