#include #include #include using namespace std; void bins(int col, int minRow, int maxRow); int n; vector vs(2e5); unsigned long long ans; int main() { cin >> n; vs.resize(n); for (int i = 0; i < n; i++) { cin >> vs[i]; } sort(vs.begin(), vs.end()); // for (int i = 0; i < n; i++) cout << vs[i] << endl; bins(0, 0, n-1); cout << ans << endl; return 0; } void bins(int col, int minRow, int maxRow) { for (char ch = 'a'; ch <= 'z'; ch++) { int lRow = 0, hRow = 0; for (int b=25; b >=0; b--) { int u = lRow | (1 << b); int v = hRow | (1 << b); if (minRow <= u && u <= maxRow) { if (vs[u].size() <= col || vs[u][col] < ch) { lRow = u; } } if (minRow <= v && v <= maxRow) { if (vs[v].size() <= col || vs[v][col] <= ch) { hRow = v; } } } if (vs[hRow].size() <= col || vs[hRow][col] != ch) { continue; } if (vs[lRow].size() <= col || vs[lRow][col] != ch) { lRow++; } unsigned long long len = hRow - lRow + 1; // cout << "[" << col << "] " << ch << ": " << lRow << ", " << hRow << ", (" << len << ")" << endl; if (len == 1ULL) { ans += (unsigned long long)vs[hRow].size() - (unsigned long long)col; } else if (len > 1ULL) { unsigned long long lp = 1, rp = len; while (lp <= rp) { ans += lp * rp * (lp == rp ? 1ULL : 2ULL); lp++; rp--; } bins(col + 1, lRow, hRow); } } }