从反面考虑，统计非单色三角形的个数。
如果从一个点出发两条不同颜色的边，那么这三个点一定构成一个非单色三角形。
枚举一个顶点，统计从这个点出发的红边的个数a[i]和蓝边的个数n - 1 - a[i]，这样以该点为顶点的非单色三角形的数目为a[i] * (n - 1 - a[i])
由于每个单色三角形计数了两次，所以总单色三角形的个数为sum{ a[i] * (n - 1 - a[i]) | 1 ≤ i ≤ n } / 2
最后一共有C(n, 3)个三角形，用总的减去所求就是答案。
#include <cstdio> const int maxn = + ;
int a[maxn][maxn]; int main()
{
//freopen("in.txt", "r", stdin); int T;
scanf("%d", &T);
while(T--)
{
int n;
scanf("%d", &n);
for(int i = ; i < n; i++)
for(int j = i + ; j <= n; j++)
{
int x;
scanf("%d", &x);
a[i][j] = a[j][i] = x;
}
long long ans1 = ;
for(int i = ; i <= n; i++)
{
int t = ;
for(int j = ; j <= n; j++) if(i != j) t += a[i][j];
ans1 += (long long)t * (n - - t);
}
long long ans2 = n * (n-) / * (n-) / ;
printf("%lld\n", ans2 - ans1 / );
} return ;
}
代码君