题目分析

有 $N$ 个选手的单循环比赛（竞赛图），要求构造一个竞赛图使得恰好有 $M$ 个三元环。

关键公式

竞赛图中三元环数量的公式为：

三元环数=(3N)−∑i=1N( 2d − (i)) 如果是三元环：入度序列是 $(1,1,1)$，那么 $\sum \binom{d^-}{2} = 0+0+0=0$，三元环数=1 如果是非三元环（传递的）：比如 1→2→3→1 不成立，传递的是 1→2, 1→3, 2→3，入度序列是 $(0,1,2)$，$\sum \binom{d^-}{2} = 0+0+1=1$，三元环数=0 所以入度序列 $(0,1,2)$ 时 $S=1$，三元环数=0；入度序列 $(1,1,1)$ 时 $S=0$，三元环数=1。

因此 $S$ 可以取不同值。

其中 $d^-(i)$ 是顶点 $i$ 的入度。

构造思路

竞赛图的入度序列是 $0,1,\dots,N-1$ 的一个排列。通过调整入度序列可以改变三元环数量：

最小三元环数：$0$（传递竞赛图）

最大三元环数：$\lfloor \frac{N^3-4N}{24} \rfloor$（当 $N$ 为奇数时）

构造方法

检查可行性：$M$ 必须在 $[0, M_{\max}]$ 范围内

从传递竞赛图开始：选手 $i$ 打败所有 $j < i$

调整边方向：通过反转某些边来增加三元环数

输出结果：用邻接矩阵形式输出

算法实现

对于 $N \leq 5000$，需要 $O(N^2)$ 的构造方法。可以通过分块调整来精确控制三元环数量。