ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#678 | #117. 【0621 模拟赛】TROKUTI | protractor | 100 | 932ms | 9684kb | C++14 | 1.1kb | 2025-06-21 15:54:08 | 2025-06-21 23:52:05 |
answer
#include<iostream>
#include<map>
#include<utility>
#include<cmath>
#define ny(x) lpow(x,mod-2)
using namespace std;
const long long int mod=1e9+7;
long long jc[300050];
long long lpow(long long x,int y)
{
long long ans=1;
while(y)
{
if(y&1) ans*=x;
x*=x;
ans%=mod;
x%=mod;
y/=2;
}
return ans;
}
long long C(int x,int y)
{
if(x<y) return 0;
return jc[x]*ny(jc[x-y])%mod*ny(jc[y])%mod;
}
void init()
{
jc[0]=1;
for(int i=1;i<=300000;i++) jc[i]=jc[i-1]*i%mod;
}
int gcd(int i,int j)
{
int l;
while(j)
{
l=i%j;
i=j;
j=l;
}
return i;
}
int n;
int t[300050],cnt;
map<pair<int,int>,int> m;
int a,b,c;
int main()
{
init();
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a>>b>>c;
int d=gcd(abs(a),abs(b));
a/=d,b/=d;
if(a<0) a*=-1,b*=-1;
if(m[make_pair(a,b)]) t[m[make_pair(a,b)]]++;
else
{
m[make_pair(a,b)]=++cnt;
t[cnt]++;
}
}
long long ans=C(n,3);
for(int i=1;i<=cnt;i++)
{
ans=((((ans-C(t[i],3))%mod+mod)%mod-C(t[i],2)*(n-t[i])%mod)%mod+mod)%mod;
}
cout<<ans;
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 3ms
memory: 5716kb
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: 4ms
memory: 5464kb
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: 3ms
memory: 5680kb
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: 2ms
memory: 5480kb
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: 3ms
memory: 5528kb
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: 2ms
memory: 5608kb
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: 5768kb
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: 7ms
memory: 5544kb
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: 7ms
memory: 5608kb
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: 5656kb
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: 5768kb
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: 6ms
memory: 5844kb
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: 19ms
memory: 5852kb
input:
10000 393478769 738556203 6827952 393478769 738556203 523642363 393478769 738556203 876852848 393478...
output:
484345046
result:
ok "484345046"
Test #14:
score: 0
Accepted
time: 272ms
memory: 9648kb
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: 20ms
memory: 5856kb
input:
10000 43150731 562981536 60415743 43150731 562981536 458963024 43150731 562981536 368003258 43150731...
output:
483275456
result:
ok "483275456"
Test #16:
score: 0
Accepted
time: 202ms
memory: 9684kb
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: 20ms
memory: 5904kb
input:
10000 226922248 948048502 664992202 226922248 948048502 970629073 226922248 948048502 51606080 22692...
output:
481876198
result:
ok "481876198"
Test #18:
score: 0
Accepted
time: 235ms
memory: 9600kb
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: 18ms
memory: 5888kb
input:
10000 176721617 620409850 489941614 816064587 763087269 5642316 816064587 763087269 362859512 816064...
output:
482006082
result:
ok "482006082"
Test #20:
score: 0
Accepted
time: 86ms
memory: 7768kb
input:
77777 23811 39430 938867730 5264 57977 305190928 7972 55269 440604468 27186 36055 980191230 29278 33...
output:
815976874
result:
ok "815976874"