ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#703 | #117. 【0621 模拟赛】TROKUTI | xuyunao | 100 | 1053ms | 18872kb | C++14 | 1.2kb | 2025-06-21 16:19:56 | 2025-06-21 23:53:19 |
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int mod = 1e9 + 7;
const int maxn = 3e5 + 10;
int a[maxn],b[maxn],c[maxn];
map<pii,int> mp;
int qpow(int x,int y)
{
int ans = 1;
while(y)
{
if(y & 1) ans = ans * x % mod;
x = x * x % mod;
y >>= 1;
}
return ans;
}
int jc[maxn],inv[maxn];
void init()
{
jc[0] = 1;
for(int i = 1;i <= 300000;i++) jc[i] = jc[i - 1] * i % mod;
inv[300000] = qpow(jc[300000],mod - 2);
for(int i = 300000 - 1;i >= 0;i--) inv[i] = inv[i + 1] * (i + 1) % mod;
inv[0] = 1;
}
int C(int n,int m)
{
if(n < m) return 0;
return jc[n] * inv[m] % mod * inv[n - m] % mod;
}
signed main()
{
init();
int n;
cin >> n;
for(int i = 1;i <= n;i++)
{
cin >> a[i] >> b[i] >> c[i];
mp[{a[i],b[i]}]++;
}
int minu = 0;
for(auto it : mp)
{
minu += C(it.second,2);
minu %= mod;
}
int cnt = 0;
int ans = 0;
for(int i = 1;i <= n;i++)
{
int x = a[i];
int y = b[i];
int ch = n - mp[{x,y}];
int xx = minu - C(mp[{x,y}],2);
ans = (ans + ((C(ch,2) + mod - xx) % mod) % mod) % mod;
}
ans = ans * qpow(3,mod - 2) % mod;
cout << ans << endl;
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 5ms
memory: 13732kb
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: 13456kb
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: 6ms
memory: 13508kb
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: 8ms
memory: 13524kb
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: 6ms
memory: 13680kb
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: 4ms
memory: 13612kb
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: 12ms
memory: 13616kb
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: 9ms
memory: 13752kb
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: 10ms
memory: 13728kb
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: 11ms
memory: 13708kb
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: 12ms
memory: 13692kb
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: 9ms
memory: 13744kb
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: 22ms
memory: 13784kb
input:
10000 393478769 738556203 6827952 393478769 738556203 523642363 393478769 738556203 876852848 393478...
output:
484345046
result:
ok "484345046"
Test #14:
score: 0
Accepted
time: 299ms
memory: 18872kb
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: 19ms
memory: 13572kb
input:
10000 43150731 562981536 60415743 43150731 562981536 458963024 43150731 562981536 368003258 43150731...
output:
483275456
result:
ok "483275456"
Test #16:
score: 0
Accepted
time: 225ms
memory: 17980kb
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: 13712kb
input:
10000 226922248 948048502 664992202 226922248 948048502 970629073 226922248 948048502 51606080 22692...
output:
481876198
result:
ok "481876198"
Test #18:
score: 0
Accepted
time: 256ms
memory: 18456kb
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: 20ms
memory: 13568kb
input:
10000 176721617 620409850 489941614 816064587 763087269 5642316 816064587 763087269 362859512 816064...
output:
482006082
result:
ok "482006082"
Test #20:
score: 0
Accepted
time: 96ms
memory: 15780kb
input:
77777 23811 39430 938867730 5264 57977 305190928 7972 55269 440604468 27186 36055 980191230 29278 33...
output:
815976874
result:
ok "815976874"