当前位置：首页 > news >正文

打卡信奥刷题（3226）用C++实现信奥题 P8398 [CCC 2022 S4] Good Triplets

news 2026/5/7 23:00:58

P8398 [CCC 2022 S4] Good Triplets

题目描述

Andrew\rm AndrewAndrew是十分好奇的学生，一天他在纸上画了一个圆，圆心在(0,0)(0,0)(0,0)。设周长为CCC，圆上每一个点的坐标为：

现在Andrew\rm AndrewAndrew在圆上画了nnn个点，第iii的点画在pip_ipi上，Andrew\rm AndrewAndrew可能在一个位置上画多个点。

现在一个好的三角形（a,b,c)（a,b,c)（a,b,c)的定义为：

1≤a<b<c≤n1\le a<b<c\le n1≤a<b<c≤n
原点（0，0）（0，0）（0，0）严格位于顶点在pap_apa，PbP_bPb和pcp_cpc的三角形内。特别注意的是，原点不在三角形的周长上。

Andrew\rm AndrewAndrew问你有多少个好的三角形。

输入格式

第一行两个整数n,cn,cn,c，表示点的个数和圆的周长。

接下来一行，有nnn个整数，具体意义见题目描述。

输出格式

输出一个整数xxx，表示有xxx个好的三角形。

输入输出样例 #1

输入 #1

8 10 0 2 5 5 6 9 0 0

输出 #1

说明/提示

样例111解释：

Andrew\rm AndrewAndrew画了下面的图：

原点严格地位于顶点为p1p_1p1、p2p_2p2和p5p_5p5的三角形内，所以（1，2，5）（1，2，5）（1，2，5）是一个好的三角形。其他五个好三联体是（2，3，6），（2，4，6），（2，5，6），（2，5，7）（2，3，6），（2，4，6），（2，5，6），（2，5，7）（2，3，6），（2，4，6），（2，5，6），（2，5，7）和（2，5，8）（2，5，8）（2，5，8）。

对于20%20\%20%的数据：3≤n≤200,3≤c≤1063\le n\le 200,3\le c\le10^63≤n≤200,3≤c≤106

对于另外20%20\%20%的数据：3≤n≤106,3≤c≤60003\le n\le 10^6,3\le c\le60003≤n≤106,3≤c≤6000

对于40%40\%40%的数据：3≤n≤106,3≤c≤1063\le n\le 10^6,3\le c\le10^63≤n≤106,3≤c≤106且所有点的位置互不相同。

对于100%100\%100%的数据：3≤n≤106,3≤c≤1063\le n\le 10^6,3\le c\le10^63≤n≤106,3≤c≤106

C++实现

#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;constintN=1e6+5;intn,c;inta[N];intcnt[N];intsum[N];longlongc2(intx){if(x<=1){return0;}return(longlong)x*(x-1)/2;}longlongc3(intx){if(x<=2){return0;}return(longlong)x*(x-1)*(x-2)/6;}intmain(){scanf("%d%d",&n,&c);for(inti=1;i<=n;i++){scanf("%d",&a[i]);cnt[a[i]]++;}intli=c/2;longlongans=0;intnow=0;for(inti=1;i<=li;i++){now+=cnt[i];}if(c%2==0){for(inti=0;i<c;i++){ans+=(longlong)cnt[i]*c2(now);ans+=(longlong)c2(cnt[i])*(now-cnt[(i+li)%c]);now-=cnt[(i+1)%c];now+=cnt[(i+li+1)%c];}}else{for(inti=0;i<c;i++){ans+=(longlong)cnt[i]*c2(now);ans+=(longlong)c2(cnt[i])*now;now-=cnt[(i+1)%c];now+=cnt[(i+li+1)%c];}}for(inti=0;i<c;i++){ans+=c3(cnt[i]);}longlongsum=c3(n);printf("%lld\n",sum-ans);return0;}