CSUST 4007-你真的会图论吗？（思维-三元环）_无向完全图 求颜色相同的三元组

题目链接：http://acm.csust.edu.cn/problem/4007
博客园食用链接：https://www.cnblogs.com/lonely-wind-/p/13439655.html

Description

给你一张完全无向图,每条边有两种颜色(黑色或者白色),你需要求出有多少个三元环,路径上边的颜色相同给你一张完全无向图,每条边有两种颜色(黑色或者白色),你需要求出有多少个三元环,路径上边的颜色相同

Input
第一行一个正整数$n$,表示这张完全图的点数.$(1\le n\le 5e3)$

第二行五个整数,$A,B,C,P,D,1\le A,B,C,P,D\le 10^9$
,且$D\le P$,然后我们规定,对于边$i,j(i<j)$,如果$(A(i+j{)}^2+B(i-j{)}^2+C)\mathrm{m}\mathrm{o}\mathrm{d}P>D$,则该边为黑色,否则为白色.

Output
输出一个数表示结果

Sample Input 1
6
2 3 4 11 5
Sample Output 1
6

正所谓正难则反，对于直接选出同色的三元环可能会不知道怎么入手，那么我们考虑将所有的三元环减去不符合条件的三元环。那么总共的三元环个数很好算，就是$C_n^3$，对于不符合条件的三元环，我们知道他们一定会有两条边颜色相异，而这两条边一定是由某个点延伸出去的，那么我们直接枚举这个点，然后再枚举他的边就好了（也就是枚举其他所有的点）

接下来的关键就是如何在一个点的所有边中计算不合法的三元环了。为了不重复，我们对该点延伸的每个边找在他前面的和他颜色互异的边，然后直接加上就好了。但所需要考虑的是重复的问题，虽然对于点内的三元环来讲没有重复了，但对于点之间的三元环就可能会出现重复了，比如说对于如下三元环而言：

2到5到6是相异的，但一定会有一个点，假设是5使得5-6，5-2同色，也一定会有一个点假设是6使得6-5，6-2异色。那么也就是一个不合法的三元环一定会重复2次计算。

那么代码也就出来了。
以下是AC代码：

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

typedef long long ll;
const int mac=5e3+10;

bool color[mac][mac];//0为白色，1为黑色

ll pw(int x) {return 1LL*x*x;}

int main(int argc, char const *argv[])
{
	int n;
	scanf ("%d",&n);
	int a,b,c,d,p;
	scanf ("%d%d%d%d%d",&a,&b,&c,&p,&d);
	for (int i=1; i<=n; i++){
		for (int j=i+1; j<=n; j++){
			ll val=(1LL*a*pw(i+j)+1LL*b*pw(i-j)+c)%p;
			if (val>d) {color[i][j]=color[j][i]=true;}
			else {color[i][j]=color[j][i]=false; }
		}
	}
	ll ans=1LL*n*(n-1)*(n-2)/6;
	ll res=0;
	for (int i=1; i<=n; i++){
		int black=0,white=0;
		for (int j=1; j<=n; j++){
			if (i==j) continue;
			if (color[i][j]) {res+=white; black++;}
			else {res+=black; white++;}
		}
	}
	ans-=res/2;
	printf("%lld\n",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37