题目传送门（内部题79）
输入格式
第一行读入两个整数$n,e$表示节点数及$cwystc$已确定的有向边边数。
接下来$e$行，每行两个整数$x,y$描述$cwystc$确定的边。
输出格式
输出一个整数表示期望陪妹子的天数。
样例
见下发文件
数据范围与提示
对于$30\%$的数据：$nleqslant 300$
对于另外i$20\%$的数据：$e=0$
对于另外$20\%$的数据：$e=frac{n imes (n-1)}{2}$
对于$100\%$的数据：$nleqslant 100,000,eleqslant 100,000$
题解
先转化一下题意，即让我们求竞赛图的期望最小环的个数。
而对于一张竞赛图，其要么是一张拓扑图，要么存在一个三元环。
因为该图不存在环，于是问题转化为三元环计数。
考虑容斥，不妨设$p[i]$表示点$i$的出度，那么对于三元组$(i,x,y){xin p[i],yin p[i],x eq y}$不组成三元环，而且这样的三元组只会在第$i$点枚举一次。
不妨再设$q[i]$表示连接点$i$未确定的边数，那么期望要减去：
$$frac{p[i] imes (p[i]-1)}{2}+p[i] imes frac{q[i]}{2}+frac{q[i] imes (1-q[i])}{2} imes frac{1}{4}$$
时间复杂度：$Theta(n+e)$。
期望得分：$100$分。
实际得分：$100$分。
代码时刻
#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
const int two=500000004;
const int six=166666668;
const int eig=125000001;
int n,e;
int du[100001],p[100001],q[100001];
long long ans;
long long qpow(long long x,long long y)
{
long long res=1;
while(y)
{
if(y&1)res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
int main()
{
scanf("%d%d",&n,&e);
while(e--)
{
int x,y;
scanf("%d%d",&x,&y);
du[x]++;du[y]++;p[x]++;
}
ans=1LL*n*(n-1)%mod*(n-2)%mod*six%mod;
for(int i=1;i<=n;i++)
{
q[i]=n-du[i]-1;
ans=(ans-1LL*p[i]*(p[i]-1)%mod*two%mod-1LL*p[i]*q[i]%mod*two%mod-1LL*q[i]*(q[i]-1)%mod*eig%mod+mod)%mod;
}
printf("%lld
",ans);
return 0;
}
rp++