F.小橙的圈圈

题解

注意到竞赛图上的三元组 共有如下两类状态：

其中的第一类（即三元环）很难枚举，因此考虑枚举第二类三元组。

具体地，我们统计朝每个点 连边的点的总数 ，则在这些点中任取一对 ，都能唯一地确定一个第二类三元组 。

因此第二类三元组的总数为 。答案即为三元组总数 减去第二类三元组的总数。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int i,j,k,n,m,t;
ll sd,res,in[5005];

int main(){
	cin>>n>>sd;
	res=1ll*n*(n-1)*(n-2)/6;
	for(i=1;i<=n;i++)for(j=i+1;j<=n;j++){
		if(sd&1)in[i]++;
		else in[j]++;
		sd=(sd*7+13)%1000000007;
	}
	for(i=1;i<=n;i++){
		res-=(in[i]-1)*in[i]/2;
	}
	cout<<res;
}