ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#542 | #117. 【0621 模拟赛】TROKUTI | lxn | 100 | 875ms | 7160kb | C++14 | 1012b | 2025-06-20 16:42:23 | 2025-06-21 23:21:05 |
answer
/*
容斥
总数-三条边平行-两条边平行
map统计每个斜率的条数。
无重合,不用管c
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = (int)1e9 + 7;
const int N = 3e5+9;
ll n,x,y,z,a[N], b[N];
map<pair<ll,ll>,ll>mp;
ll C3(ll x) {
return x * (x - 1) / 2* (x - 2) / 3%mod;
}
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}
int main() {
cin>>n;
for (int i = 1; i <= n; ++i) {
cin>>x>>y>>z;
if (x == 0)y=1;
else if (y== 0)x = 2e9;
else {
ll d = gcd(x, y);
x /= d;
y /= d;
}
++mp[ make_pair(x,y)];
}
ll ans = C3(n);
for (auto it : mp) {
ll cnt = it.second;
if (cnt >= 2)
ans -= cnt*(cnt-1)/2* (n - cnt) ;
if (cnt >= 3)
ans -= C3(cnt) ;
// ans%= mod;
}
ans%=mod;
ans=(ans+mod)%mod;
cout<<ans<<"\n";
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1ms
memory: 3232kb
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: 0ms
memory: 3384kb
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: 3288kb
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: 3448kb
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: 3448kb
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: 1ms
memory: 3376kb
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: 3564kb
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: 3464kb
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: 6ms
memory: 3424kb
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: 6ms
memory: 3464kb
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: 3304kb
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: 5ms
memory: 3424kb
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: 17ms
memory: 3552kb
input:
10000 393478769 738556203 6827952 393478769 738556203 523642363 393478769 738556203 876852848 393478...
output:
484345046
result:
ok "484345046"
Test #14:
score: 0
Accepted
time: 260ms
memory: 6936kb
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: 14ms
memory: 3304kb
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: 7160kb
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: 16ms
memory: 3556kb
input:
10000 226922248 948048502 664992202 226922248 948048502 970629073 226922248 948048502 51606080 22692...
output:
481876198
result:
ok "481876198"
Test #18:
score: 0
Accepted
time: 225ms
memory: 6880kb
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: 17ms
memory: 3252kb
input:
10000 176721617 620409850 489941614 816064587 763087269 5642316 816064587 763087269 362859512 816064...
output:
482006082
result:
ok "482006082"
Test #20:
score: 0
Accepted
time: 80ms
memory: 5392kb
input:
77777 23811 39430 938867730 5264 57977 305190928 7972 55269 440604468 27186 36055 980191230 29278 33...
output:
815976874
result:
ok "815976874"