QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#398351#3764. String CommutativitySamponYW#AC ✓208ms12216kbC++141.7kb2024-04-25 11:02:592024-04-25 11:03:00

Judging History

This is the latest submission verdict.

  • [2024-04-25 11:03:00]
  • Judged
  • Verdict: AC
  • Time: 208ms
  • Memory: 12216kb
  • [2024-04-25 11:02:59]
  • Submitted

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