提出 #15780880

---

ソースコード 拡げる

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

const ll MOD = 3006703054056749LL;

struct Modint {
  ll val;
  
  Modint (ll _val = 0)
    : val(_val % MOD) {}

  Modint operator+ (Modint other) const {
    return Modint(val + other.val);
  }

  void operator+= (Modint other) {
    val += other.val;
    val %= MOD;
  }

  Modint operator- () const {
    return Modint(MOD - val);
  }

  Modint operator- (Modint other) const {
    return Modint(val + MOD - other.val);
  }

  void operator-= (Modint other) {
    val += MOD - other.val;
    val %= MOD;
  }

  Modint operator* (Modint other) const {
    return Modint(val * other.val);
  }

  void operator*= (Modint other) {
    val *= other.val;
    val %= MOD;
  }

  bool operator== (Modint other) const {
    return val == other.val;
  }

  bool operator!= (Modint other) const {
    return val != other.val;
  }
};

ostream& operator<< (ostream& out, Modint p) {
  out << p.val;
  return out;
}

const int MAX_N = 2e5 + 5;
const Modint BASE (231);

ll ans;
string s [MAX_N];
vector<int> rewards [MAX_N];
map<ll, int> fst;

bool has (const set<pair<char, int>> &exist, char val) {
  auto lb = exist.lower_bound(make_pair(val, -1));
  if (lb == exist.end()) return false;
  return lb->first == val;
}

void proc (int idx) {
  int n = s[idx].size();
  set<pair<char, int>> exist;
  for (int i = 0; i < n; i++) {
    exist.insert(make_pair(s[idx][i], i));
  }

  Modint hsh (0);
  if (fst.count(hsh.val)) {
    int udx = fst[hsh.val];
    for (int c = 0; c < 26; c++) {
      if (has(exist, c + 'a')) {
        ans += rewards[udx][c];
      }
    }
  }

  for (int i = n - 1; i > 0; i--) {
    hsh *= BASE;
    hsh += Modint(s[idx][i]);
    exist.erase(make_pair(s[idx][i], i));

    if (fst.count(hsh.val)) {
      int udx = fst[hsh.val];
      for (int c = 0; c < 26; c++) {
        if (has(exist, c + 'a')) {
          ans += rewards[udx][c];
        }
      }
    }
  }

  if (!fst.count(hsh.val)) {
    fst[hsh.val] = idx;
    rewards[idx] = vector<int> (26, 0);
  }
  rewards[fst[hsh.val]][s[idx][0] - 'a']++;
}

int main () {
  ios::sync_with_stdio(false);

  int n;
  cin >> n;

  vector<pair<int, int>> lengths;
  for (int i = 0; i < n; i++) {
    cin >> s[i];
    lengths.push_back(make_pair((int) s[i].size(), i));
  }

  sort(lengths.begin(), lengths.end());

  for (auto pr : lengths) {
    proc(pr.second);
  }

  cout << ans << endl;
}

提出情報

ジャッジ結果