ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#749 | #117. 【0621 模拟赛】TROKUTI | wyz | 100 | 866ms | 15872kb | C++14 | 850b | 2025-06-21 16:50:22 | 2025-06-21 23:55:50 |
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+10;
const int P=1e9+7;
struct Line
{
int al,bl,cl;
}x[N];
int fgcd(int a,int b)
{
if(b==0)return a;
return fgcd(b,a%b);
}
bool cmp(Line a,Line b)
{
if(a.al==b.al)return a.bl>b.bl;
return a.al>b.al;
}
int n,m,ans;
int s[N],h[N],a[N];
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int a,b,c;
cin>>a>>b>>c;
int k=fgcd(a,b);
a=a/k,b=b/k;
x[i].al=a,x[i].bl=b,x[i].cl=c;
}
sort(x+1,x+n+1,cmp);
for(int i=1;i<=n;i++)
{
if(x[i].al==x[i-1].al&&x[i].bl==x[i-1].bl)
a[m]++;
else
{
m++;
a[m]++;
}
}
for(int i=1;i<=m;i++)s[i]=s[i-1]+a[i];
for(int i=m-1;i>1;i--)h[i]=(s[m]-s[i])*a[i]+h[i+1];
for(int i=2;i<m;i++)ans=(ans+a[i-1]*h[i]+P)%P;
cout<<(ans+P)%P<<endl;
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 2ms
memory: 9396kb
input:
500 73102 49767 81374 73102 49767 92538 73102 49767 13140 73102 49767 24384 73102 49767 27887 17295 ...
output:
20377848
result:
ok "20377848"
Test #2:
score: 0
Accepted
time: 1ms
memory: 9496kb
input:
500 124 63117 7826508 7035 56206 395409210 11693 51548 602750764 9043 54198 490112514 12433 50808 63...
output:
11783400
result:
ok "11783400"
Subtask #2:
score: 10
Accepted
Test #3:
score: 10
Accepted
time: 1ms
memory: 9464kb
input:
500 161481 156950 868380 161481 156950 129078 161481 156950 461965 161481 156950 884496 161481 15695...
output:
20354576
result:
ok "20354576"
Test #4:
score: 0
Accepted
time: 0ms
memory: 9440kb
input:
500 54987 8254 453862698 22821 40420 922424820 55211 8030 443344330 7995 55246 441691770 7536 55705 ...
output:
11783400
result:
ok "11783400"
Subtask #3:
score: 10
Accepted
Test #5:
score: 10
Accepted
time: 2ms
memory: 9492kb
input:
500 1616 7821 6023 1616 7821 1348 1616 7821 1311 1616 7821 8768 1616 7821 3224 1041 342 8905 1041 34...
output:
20376818
result:
ok "20376818"
Test #6:
score: 0
Accepted
time: 0ms
memory: 9596kb
input:
500 28122 35119 987616518 39998 23243 929673514 6803 56438 383947714 10419 52822 550352418 4210 5903...
output:
11783400
result:
ok "11783400"
Subtask #4:
score: 10
Accepted
Test #7:
score: 10
Accepted
time: 8ms
memory: 9508kb
input:
5000 389677 811320 494924 389677 811320 749898 444969 181234 734834 444969 181234 901259 444969 1812...
output:
787588230
result:
ok "787588230"
Test #8:
score: 0
Accepted
time: 6ms
memory: 9508kb
input:
5000 23083 40158 926967114 60406 2835 171251010 24995 38246 955958770 29023 34218 993109014 3991 592...
output:
828333923
result:
ok "828333923"
Subtask #5:
score: 10
Accepted
Test #9:
score: 10
Accepted
time: 5ms
memory: 9568kb
input:
5000 879363 278076 350260 879363 278076 59028 879363 278076 651081 879363 278076 693725 879363 27807...
output:
787932788
result:
ok "787932788"
Test #10:
score: 0
Accepted
time: 7ms
memory: 9572kb
input:
5000 37905 25336 960361080 35770 27471 982637670 52420 10821 567236820 30663 32578 998939214 45883 1...
output:
828333923
result:
ok "828333923"
Subtask #6:
score: 10
Accepted
Test #11:
score: 10
Accepted
time: 8ms
memory: 9608kb
input:
5000 723822 556273 863546 723822 556273 609176 150507 44473 252270 150507 44473 584705 478150 568821...
output:
787762934
result:
ok "787762934"
Test #12:
score: 0
Accepted
time: 7ms
memory: 9456kb
input:
5000 39891 23350 931454850 16346 46895 766545670 33352 29889 996857928 11336 51905 588395080 43183 2...
output:
828333923
result:
ok "828333923"
Subtask #7:
score: 10
Accepted
Test #13:
score: 10
Accepted
time: 18ms
memory: 9524kb
input:
10000 393478769 738556203 6827952 393478769 738556203 523642363 393478769 738556203 876852848 393478...
output:
484345046
result:
ok "484345046"
Test #14:
score: 0
Accepted
time: 261ms
memory: 15872kb
input:
300000 31401 31840 999807840 54120 9121 493628520 46872 16369 767247768 60349 2892 174529308 31055 3...
output:
990696070
result:
ok "990696070"
Subtask #8:
score: 10
Accepted
Test #15:
score: 10
Accepted
time: 16ms
memory: 9512kb
input:
10000 43150731 562981536 60415743 43150731 562981536 458963024 43150731 562981536 368003258 43150731...
output:
483275456
result:
ok "483275456"
Test #16:
score: 0
Accepted
time: 192ms
memory: 14212kb
input:
210000 56426 6815 384543190 17171 46070 791067970 31577 31664 999854128 10214 53027 541617778 27620 ...
output:
695778049
result:
ok "695778049"
Subtask #9:
score: 10
Accepted
Test #17:
score: 10
Accepted
time: 17ms
memory: 9516kb
input:
10000 226922248 948048502 664992202 226922248 948048502 970629073 226922248 948048502 51606080 22692...
output:
481876198
result:
ok "481876198"
Test #18:
score: 0
Accepted
time: 224ms
memory: 14652kb
input:
249243 17136 46105 790055280 49548 13693 678460764 6857 56384 386625088 32641 30600 998814600 26037 ...
output:
916345391
result:
ok "916345391"
Subtask #10:
score: 10
Accepted
Test #19:
score: 10
Accepted
time: 15ms
memory: 9528kb
input:
10000 176721617 620409850 489941614 816064587 763087269 5642316 816064587 763087269 362859512 816064...
output:
482006082
result:
ok "482006082"
Test #20:
score: 0
Accepted
time: 76ms
memory: 11796kb
input:
77777 23811 39430 938867730 5264 57977 305190928 7972 55269 440604468 27186 36055 980191230 29278 33...
output:
815976874
result:
ok "815976874"