1 条题解
-
0
如果直接数同色的，可以采用三元环计数，由于是完全图，考虑用 bitset 优化，时间复杂度 ，可以通过 的数据点。
考虑容斥，不合法的三元环要么是两黑一白，要么是两白一黑。
发现有一个共同点就是一白一黑。
所以对于一个点，直接找一条白边，找一条黑边就是全部的方案数，最后再除以二。
总方案数是 。
代码
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; int n,m,s[N]; long long ans; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); s[x]++,s[y]++; } for(int i=1;i<=n;i++)ans=ans+1ll*s[i]*(n-1-s[i]); printf("%lld",1ll*n*(n-1)*(n-2)/6-ans/2); }
- 1
