三角形 题解

2019-07-12 10:34:28


本来这题是 $n\leq 10^6$的,然后有人跟我说太简单了,然后就改成 $n\leq 10^{18}$了.所以毒瘤不要怪我

容斥,所求即

$$ \sum\limits_{i,j,k}[1\leq i\leq j\leq k][i+j+k=n][i+j>k] $$

先算出

$$ \sum\limits_{i,j,k}[1\leq i\leq j\leq k][i+j+k=n] $$

这东西可以这么算:

$$ \frac{1}{6}\left(\binom{n-1}{2}+3\left\lfloor\frac{n-1}{2}\right\rfloor+2[3\mid n]\right) $$

原理是先不考虑 $i\leq j\leq k$,此时答案就是 $\binom{n-1}{2}$,这样 $i<j<k$的算了 $6$次, $i=j<k$的和 $i<j=k$的算了 $3$次, $i=j=k$的算了一次.然后再算有两个相等的情况,此时答案是 $\left\lfloor\frac{n-1}{2}\right\rfloor$,这里面把 $i=j=k$的也算了一次.拼凑一下就得到上面那个东西了..

然后再考虑 $$ \begin{aligned}&\sum\limits_{i,j,k}[1\leq i\leq j\leq k][i+j+k=n][i+j\leq k]\\=&\sum\limits_{i,j,k}[1\leq i\leq j][i+j\leq n-i-j][i+j+k=n]\\=&\sum\limits_{i,j,k}[1\leq i\leq j][2\leq i+j\leq\frac{n}{2}][k=n-i-j]\\=&\sum\limits_{i+j=2}^{\left\lfloor\frac{n}{2}\right\rfloor}\sum\limits_{i,j}[1\leq i\leq j]\\=&\sum\limits_{t=2}^{\left\lfloor\frac{n}{2}\right\rfloor}\left\lfloor\frac{t}{2}\right\rfloor\\=&\sum_{i\geq 1}[2i\leq \frac{n}{2}]\left\lfloor\frac{2i}{2}\right\rfloor+\sum_{i\geq 1}[2i+1\leq \frac{n}{2}]\left\lfloor\frac{2i+1}{2}\right\rfloor\\=&\sum\limits_{i=1}^{\left\lfloor\frac{n}{4}\right\rfloor}i+\sum\limits_{i=1}^{\left\lfloor\frac{n-2}{4}\right\rfloor}i\\=&\frac{1}{2}\left\lfloor\frac{n}{4}\right\rfloor(\left\lfloor\frac{n}{4}\right\rfloor+1)+\frac{1}{2}\left\lfloor\frac{n-2}{4}\right\rfloor\left\lfloor\frac{n+2}{4}\right\rfloor\end{aligned} $$ 总的式子 $$ ans=\frac{1}{6}\left(\frac{1}{2}(n-1)(n-2)+3\left\lfloor\frac{n-1}{2}\right\rfloor+2[3\mid n]\right)-\frac{1}{2}\left\lfloor\frac{n}{4}\right\rfloor(\left\lfloor\frac{n}{4}\right\rfloor+1)-\frac{1}{2}\left\lfloor\frac{n-2}{4}\right\rfloor\left\lfloor\frac{n+2}{4}\right\rfloor $$