Submission #1077344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077344		komasan	Lozinke (COCI17_lozinke)	C++14	100 / 100	187 ms	23380 KiB

lozinke

#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);


    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;

}

• Subtask 1: 100 / 100