#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int , int>
#define fi first
#define se second
#define endl '\n'
const int INF = (int)1e9;
const int maxn = 20000 + 6;
const int mod = 1e9 + 7;
int n;
string a[maxn];
const int base = 311;
const int nmod = 2;
const int ModHash[4] = {(int)1e9 + 2277 , (int)1e9 + 5277 , (int)1e9 + 8277 , (int)1e9 + 9277};
ll pw[maxn][nmod];
void prepare(int n)
{
for (int i = 0 ; i < nmod ; ++i) pw[0][i] = 1;
for (int i = 1 ; i <= n ; ++i)
for (int j = 0 ; j < nmod ; ++j) pw[i][j] = pw[i - 1][j] * base % ModHash[j];
}
struct HASH{
vector<vector<ll>> HashVal;
void BuildHash(string s)
{
int n = s.size();
HashVal.resize(n + 1);
for (int i = 0 ; i <= n ; ++i) HashVal[i].resize(nmod);
for (int i = 1 ; i <= n ; ++i)
for (int j = 0 ; j < nmod ; ++j)
HashVal[i][j] =( HashVal[i - 1][j] * base + (int)s[i - 1]) % ModHash[j];
}
ll get(int l , int r , int pos)
{
return (HashVal[r][pos] - HashVal[l - 1][pos] * pw[r - l + 1][pos] % ModHash[pos] + ModHash[pos]) % ModHash[pos];
}
} h[maxn];
map<pii , int> m;
ll ans = 0;
void calc(int id)
{
int n = a[id].size();
map<pii , bool> mark;
for (int i = 1 ; i <= n ; ++i)
for (int j = i ; j <= n ; ++j)
{
if ( mark[{ h[id].get(i , j , 0) , h[id].get(i , j , 1)}] == 0)
{
ans += m[{ h[id].get(i , j , 0) , h[id].get(i , j , 1)}];
mark[{ h[id].get(i , j , 0) , h[id].get(i , j , 1)}] = 1;
}
// if (m[{ h[id].get(i , j , 0) , h[id].get(i , j , 1)}])
// cout << id << " " << i << " " << j << " " << ans << endl;
}
m[{ h[id].get(1 , n , 0) , h[id].get(1 , n , 1) } ]++;
// cerr << id << " " << m[{ h[3].get(1 , 1 , 0) , h[3].get(1 , 1 , 1) } ] << " " << m[{ h[1].get(1 , 1 , 0) , h[1].get(1 , 1 , 1) } ]<< endl;
// cerr << a[3][0] << " " << a[1][0] << endl;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("PASS.INP" , "r" , stdin);
// freopen("PASS.OUT" , "w" , stdout);
prepare(15);
cin >> n ;
for (int i = 1 ; i <= n ; ++i) cin >> a[i];
sort(a + 1 , a + n + 1 , [&](string a , string b)
{
return (a.size() != b.size() ? a.size() < b.size() : a < b);
});
// for (int i = 1 ; i <= n ; ++i) cout << a[i] << endl;
for (int i = 1 ; i <= n ; ++i) h[i].BuildHash(a[i]);
for (int i = 1 ; i <= n ; ++i) calc(i);
for (int i = 1 ; i <= n ; ++i)
{
int cnt = m[{ h[i].get(1 , a[i].size() , 0) , h[i].get(1 , a[i].size() , 1) } ];
ans += (cnt - 1);
m[{ h[i].get(1 , a[i].size() , 0) , h[i].get(1 , a[i].size() , 1) } ]--;
}
cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1368 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1628 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1628 KB |
Output is correct |
| 5 |
Correct |
6 ms |
2016 KB |
Output is correct |
| 6 |
Correct |
10 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
11 ms |
3016 KB |
Output is correct |
| 8 |
Correct |
18 ms |
3932 KB |
Output is correct |
| 9 |
Correct |
43 ms |
6708 KB |
Output is correct |
| 10 |
Correct |
84 ms |
11644 KB |
Output is correct |
| 11 |
Correct |
67 ms |
9816 KB |
Output is correct |
| 12 |
Correct |
251 ms |
22216 KB |
Output is correct |
| 13 |
Correct |
87 ms |
13172 KB |
Output is correct |
| 14 |
Correct |
164 ms |
20048 KB |
Output is correct |
| 15 |
Correct |
241 ms |
23408 KB |
Output is correct |
| 16 |
Correct |
70 ms |
13392 KB |
Output is correct |
| 17 |
Correct |
36 ms |
13912 KB |
Output is correct |
| 18 |
Correct |
29 ms |
11604 KB |
Output is correct |
| 19 |
Correct |
129 ms |
16060 KB |
Output is correct |
| 20 |
Correct |
40 ms |
10076 KB |
Output is correct |
