2021牛客暑期多校训练营6 C Delete Edges

题目概述

给出一个$n$个点的完全图，删除一些三元环使得剩下的边数少于$n$条。

数据范围

$$3 \leq n \leq 2000$$

分析与解

这个题实在是一个构造题。说来惭愧，并不知道这个转化为何是正确的。值得记得就是递推的证明方法。

根据题解，问题转化为

求$1\leq x<y<z\leq n$范围内满足$x+y+z\equiv 0(mod\;n)$​的方案组数。

记答案为$f(n)$，下面证明该式具有递推$f(n+3)=f(n)+n$

证明的思路在于考虑答案的来源：$x+y+z=n$和$x+y+z=2n$两种情况。假设前一种情况的答案贡献为$ans1$，第二种情况对答案的贡献为$ans2$。

下面考虑将$n$时的$ans1,ans2$递推到$n+3$时的情况。

$$1 \leq x<y<z \leq n,&x+y+z=n:ans1\\ &(x+1)+(y+1)+(z+1)=n+3\\ 2 \leq x<y<z\leq n+1,&x+y+z=n:ans1\\$$

当$z=n+2,n+3$时无解，当$x=1$时，满足$y+z=n+2$新增$[\frac{n-1}{2}]$组解，故得到

$$1 \leq x<y<z \leq n+3,x+y+z=n:ans1+\lfloor \frac{n-1}{2} \rfloor$$

再考虑$ans2的递推。

$$1 \leq x<y<z \leq n,&x+y+z=2n:ans2\\ &(x+2)+(y+2)+(z+2)=2(n+3)\\ 3 \leq x<y<z \leq n+2,&x+y+z=2(n+3):ans2\\$$

当$x=1,2$时无解，当$z=n+3$时，$x+y=n+3$，有$\lfloor \frac{n+2}{2} \rfloor$组解。

故得到

$$1 \leq x<y<z \leq n+3,x+y+z=2n:ans2+\lfloor \frac{n+2}{2} \rfloor$$

因此总共新增$\lfloor\frac{n-1}{2}\rfloor+\lfloor\frac{n+2}{2}\rfloor=n$组解。递推由此得证。

再通过递推式结合$f(3)=1,f(4)=1,f(5)=2$初始值，得到通项公式：

$$ans[n]= \begin{cases} \frac{n^2-3n+6}{6},3|n\\ \frac{n^2-3n+2}{6},3\nmid n \end{cases}$$