自动搬运

查看原文

来自洛谷，原作者为

	船酱魔王 如花美眷，似水流年

搬运于2025-08-24 22:38:44，当前版本为作者最后更新于2023-04-26 15:30:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8398 [CCC2022 S4] Good Triplets 题解

题意回顾

在一个圆上，逆时针等距分布着 $c$ 个点，我们放置一些关键点，当一个以关键点为三个顶点的非退化三角形且内部包含原点时称其为好三角形，统计所有好三角形的个数。

$3 \le n,c \le 10^6$。

分析

正难则反。

我们尝试统计内部不包含原点的三角形，再用任选出三个点的总数减去。

我们发现当一个三角形在圆的半径的一边时，一定为不合法，否则为合法。

我们假设一条直线为圆的半径，每次统计出以 $i$ 为顶点之一且剩下的顶点都在以直线为分割，与 $i$ 同侧的半圆中的三角形个数，要维护当前半圆内的点数总和，再将直线旋转一格。

注意 $c$ 奇偶的分类讨论，以及 long long 的使用。

AC 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6 + 5;
int n, c;
int a[N];
int cnt[N];
int sum[N];
long long c2(int x) {
	if(x <= 1) {
		return 0;
	}
    return (long long)x * (x - 1) / 2;
}
long long c3(int x) {
    if(x <= 2) {
        return 0;
    }
    return (long long)x * (x - 1) * (x - 2) / 6;
}
int main() {
    scanf("%d%d", &n, &c);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        cnt[a[i]]++;
    }
    int li = c / 2;
    long long ans = 0;
    int now = 0;
    for(int i = 1; i <= li; i++) {
        now += cnt[i];
    }
    if(c % 2 == 0) {
    	for(int i = 0; i < c; i++) {
        	ans += (long long)cnt[i] * c2(now);
        	ans += (long long)c2(cnt[i]) * (now - cnt[(i + li) % c]);
        	now -= cnt[(i + 1) % c];
        	now += cnt[(i + li + 1) % c];
    	}
	} else {
		for(int i = 0 ; i < c; i++) {
			ans += (long long)cnt[i] * c2(now);
			ans += (long long)c2(cnt[i]) * now;
			now -= cnt[(i + 1) % c];
			now += cnt[(i + li + 1) % c];
		}
	}
    for(int i = 0; i < c; i++) {
        ans += c3(cnt[i]);
    }
    long long sum = c3(n);
    printf("%lld\n", sum - ans);
    return 0;
}