QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#398351 | #3764. String Commutativity | SamponYW# | AC ✓ | 208ms | 12216kb | C++14 | 1.7kb | 2024-04-25 11:02:59 | 2024-04-25 11:03:00 |
Judging History
answer
#include <bits/stdc++.h>
#define db double
#define il inline
#define re register
#define ll long long
#define ui unsigned
#define ull ui ll
#define i128 __int128
#define pii pair<int, int>
#define fi first
#define se second
#define eb emplace_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define mems(v, x) memset(v, x, sizeof(v))
#define memc(a, b) memcpy(a, b, sizeof(a))
#define FOR(i, L, R) for(re int i = (L); i <= (R); ++i)
#define ROF(i, R, L) for(re int i = (R); i >= (L); --i)
#define LS i << 1, l, mid
#define RS i << 1 | 1, mid + 1, r
#define popc(x) __builtin_popcount(x)
using namespace std;
#define N 1000005
#define P 1000000007
il int add(int x, int y) {return x + y < P ? x + y : x + y - P;}
il void addr(int &x, int y) {(x += y) >= P && (x -= P);}
il int qpow(int p, int n = P - 2) {
int s = 1;
while(n) {
if(n & 1) s = 1ll * s * p % P;
p = 1ll * p * p % P, n >>= 1;
}
return s;
}
// s[i] * (pw[j] - 1) = s[j] * (pw[i] - 1)
int b[N], ib[N];
int n, s[N];
il ll calc(ll x) {return x * (x - 1) / 2;}
il void WORK() {
ll ans = 0;
FOR(i, 1, n) {
string str; cin >> str, s[i] = 0;
for(auto c : str) s[i] = add(s[i] * 131ll % P, c);
s[i] = 1ll * s[i] * ib[SZ(str)] % P;
}
sort(s + 1, s + 1 + n);
for(re int l = 1, r; l <= n; l = r + 1) {
for(r = l; r < n && s[r + 1] == s[r]; ++r);
ans += calc(r - l + 1);
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
b[0] = 1; FOR(i, 1, N - 5) b[i] = 131ll * b[i - 1] % P;
FOR(i, 0, N - 5) ib[i] = qpow(b[i] - 1);
while(cin >> n) WORK();
cerr << 1.0 * clock() / CLOCKS_PER_SEC;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 208ms
memory: 12216kb
input:
2 a ab 2 ab ab 3 a aa aaa 100 gghj dghj ajgh djch ajgh djcjdjcj dghj djcj ggdj dghj djch dghj djch gghjgghj ajchajch djcf ajgh djcf dghj djchdjch gghj ajch ajch djch djcf dgcj djch djch djcj djch ggdjggdj ggdj ajch djcj ajch ajgh dghj ajgh ggdj dgcj ajch ajghajghajgh dgcj dacj dgcjdgcj gghj gghj ggd...
output:
0 1 3 499 544 497 508 926 864 674 954 688 787 588 798 851 985 544 599 656 594 1639 1215 849 833 574 583 652 593 1192 482 480 474 634 696 501 847 488 560 868 577 1269 736 706 478 699 774 749 501 693 517 632 579 1084 477 554 572 707 795 687 673 560 602 1266 538 675 489 580 721 635 746 700 569 914 1070...
result:
ok 2209 lines