竞赛图三元环期望个数

题意

给定$n$个点的竞赛图,有$m$条边的方向是确定的,剩下的边方向不确定,问期望三元环个数

题解

如果一个点$u$有两条已经确定的出边$(u,x),(u,y)$
那么这组边一定无法构成三元环
所以我们记录每个点的已经确定的出度$d$,出度+入度$p$
那么答案就是$ans=C_{3}^{n}-\sum_{u=1}^{n}{C_{2}^{d_u}}+ d_u\times \frac{n-p_u}{2}+ \frac{C_{2}^{n-p_u}}{4}$