Submission #884325

#	Time	Username	Problem	Language	Result	Execution time	Memory
884325		vjudge1	Lozinke (COCI17_lozinke)	C++17	20 / 100	59 ms	11564 KiB

lozinke

#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
#define int long long
#define vi vector<int>
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
#define pii pair<int,int>
const int N = 2e5+1;
const int B = 184871427;
const int MOD = 1e9+7;
int add(int x,int y) {return ((x+y>=MOD)?x+y-MOD:x+y);}
int mult(int x,int y) {return ((x%MOD)*(y%MOD))%MOD;}
int expo(int x,int y) {
  if (!y) return 1;
  int e = expo(x,y/2);
  e = mult(e,e);
  if (y&1) e = mult(e,x);
  return e;
}
void solve() {
  int n;
  cin >> n;
  unordered_map<string,int> ss;
  F(i,n) {
    string s;
    cin >> s;
    ss[s]++;
  } 
  int ans = 0;
  for (auto it : ss) ans+=it.second*(it.second-1);
  vector<string> strs = {""};
  for (auto it : ss) strs.push_back(it.first);
  sort(strs.begin(),strs.end(),[](string s,string t){return s.size()<t.size();});
  n = strs.size()-1;
  unordered_map<int,int> occ;
  F(i,n) {
    string s = strs[i];
    int nn = s.size();
    vi hsh(nn+1);
    hsh[0] =0 ;
    for (int i=1;i<=nn;i++) hsh[i] = add(mult(hsh[i-1],B),s[i-1]);
    for (int L=1;L<=nn;L++) {
      for (int R=L;R<=nn;R++) {
        ans+=ss[s]*occ[add(hsh[R],MOD-mult(expo(B,R-L+1),hsh[L-1]))];
      }
    }
    occ[hsh[nn]]+=ss[s];
  }
  cout << ans << endl;
}
    
                  
                             
signed main() { 
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  #ifdef Local
  freopen("in","r",stdin);
  freopen("out","w",stdout); 
  #endif
  int t = 1;
  //cin >> t;
	F(i,t) solve();
}

• Subtask 1: 20 / 100