З'єднання масивів#12304

З'єднання масивів (Розбір)

Автор проблеми:	De3b0o
Підготовлено:	De3b0o
Редаговано:	Hasan Saleh (MathModel)

Рішення

Позначимо $o v (i, j)$ ov(i,j) як максимальне перекриття між масивами $i$ та $j$ (довжина найдовшого суфікса масиву $i$ , який також є префіксом масиву $j$ ) і $m$ як суму розмірів усіх масивів.

Ми можемо бачити, що розмір з'єднання масивів $i$ та $j$ дорівнює $s z_{i} + s z_{j} + o v (i, j)$ sz_i + sz_j + ov(i,j).

Отже, очікуваний розмір з'єднання двох випадкових масивів дорівнює:

$\frac{\sum _{i = 1}^{n} \sum _{j = 1}^{n} s z _{i} + s z _{j} + o v ( i , j )}{n ^{2}}$ \frac{\sum_{i=1}^{n} \sum_{j=1}^{n} sz_i + sz_j + ov(i,j)}{n^2} Що дорівнює $\frac{2 n \cdot m + \sum _{i = 1}^{n} \sum _{j = 1}^{n} o v ( i , j )}{n ^{2}}$ \frac{2n \cdot m + \sum_{i=1}^{n} \sum_{j=1}^{n} ov(i,j)}{n^2}

Тепер, щоб обчислити $\sum_{i = 1}^{n} \sum_{j = 1}^{n} o v (i, j)$ \sum_{i=1}^{n} \sum_{j=1}^{n} ov(i,j):

Ми можемо для кожного суфікса кожного масиву $i$ підрахувати, скільки масивів $j$ мають цей суфікс як префікс, використовуючи хешування.

І щоб уникнути повторного підрахунку (оскільки масиви $i$ та $j$ можуть перекриватися в кількох точках, і нас цікавить лише той, що має максимальну довжину), для кожного $i$ ми використовуємо один з наступних підходів залежно від розміру масиву $i$ .

Підхід $1$ ( $s z_{i} \leq m$ sz_i \le \sqrt m):

Для всіх суфіксів $s 1, s 2$ ( $1 \leq s 1 < s 2 \leq n$ 1 \le s1 < s2 \le n), де суфікс $j$ означає всі елементи від $j$ до $s z_{i}$ sz_i.

Якщо перші $s z_{i} - s 2 + 1$ sz_i - s2 +1 елементів суфікса $s 1$ дорівнюють суфіксу $s 2$ , тоді всі масиви, які перекриваються з масивом $i$ в точці $s 1$ (масиви, які мають суфікс $s 1$ як префікс), також перекриваються в точці $s 2$ .

Ми можемо перевірити за O(1), використовуючи хешування.

І оскільки ми вже знаємо, скільки масивів $j$ перекриваються в точці $s 1$ , ми віднімемо цю кількість від кількості масивів, які перекриваються в точці $s 2$ , щоб позбутися повторного підрахунку.

Підхід $2$ ( $s z_{i} > m$ sz_i > \sqrt m):

Оскільки може бути не більше $m$ \sqrt m, які задовольняють цю умову, ми можемо для кожного з них пройтися по всіх префіксах усіх масивів і перевірити, чи вони перекриваються тут.

Складність $O (m \cdot m)$ \mathcal{O}(m \cdot \sqrt m).


#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define pll pair<ll, ll>
#define lin cout << "\n";
#define mid ((l + r) / 2)
#define lc (2 * x)
#define rc (2 * x + 1)
#define double long double

using namespace std;

const ll N = 1e6+9 , m = 1e9+7;

ll mod(ll x , ll md)
{
    ll y = x;
    y%=md;
    y+=md;
    y%=md;
    return y;
}

ll fp(ll x , ll y , ll md)
{
    if(y==0)
        return 1;
    ll z = fp(x,y/2,md);
    if(y%2)
        return z*z%md*x%md;
    else
        return z*z%md;
}

ll inv(ll x , ll md)
{
    return fp(x,md-2,md);
}

ll n,ans,o;
vector<ll> a[N];
ll sz[N];
vector<ll> v1,v2,pre1[N],pre2[N],suf1[N],suf2[N],pr[N];
map<pll,ll> mp;
ll p1 = 4141 , p2 = 61 , m1 = 1e9+7 , m2 = 1e9+9;
ll lim = 200;
ll inv1 = inv(p1,m1),inv2 = inv(p2,m2);
ll fh1 , fh2 , sh1 , sh2 , mn;
ll pe1 , pe2 , h1 , h2 , d;

int main()
{
    d3
    ll T = 1;
    cin >> T;
    while(T--)
    {
        mp.clear();v1.clear();v2.clear();
        ans=0;
        o=0;
        cin >> n;
        for(int i = 1 ; n>=i ; i++)
        {
            a[i].clear();
            cin >> sz[i];
            a[i].pb(0);
            for(int j = 1 ; sz[i]>=j ; j++)
            {
                ll x;
                cin >> x;
                a[i].pb(x);
            }
        }
        for(int i = 1 ; n>=i ; i++)
        {
            pre1[i].clear();pre2[i].clear();suf1[i].clear();suf2[i].clear();pre1[i].pb(0);pre2[i].pb(0);suf1[i].pb(0);suf2[i].pb(0);
            ans+=sz[i];
            if(sz[i]<lim)
                v1.pb(i);
            else
                v2.pb(i);
            h1 = 0 , h2=0;
            pe1 = 1 , pe2 = 1;
            for(ll j = 1 ; a[i].size()>j ; j++)
            {
                d = a[i][j];
                h1+=pe1*d;
                pe1*=p1;
                h2+=pe2*d;
                pe2*=p2;
                h1=mod(h1,m1);
                h2=mod(h2,m2);
                pe1=mod(pe1,m1);
                pe2=mod(pe2,m2);
                mp[{h1,h2}]++;
                pre1[i].pb(h1);
                pre2[i].pb(h2);
            }
            for(ll j = 1 ; a[i].size()>j ; j++)
            {
                suf1[i].pb(h1);
                suf2[i].pb(h2);
                d = a[i][j];
                h1=mod(h1-d,m1);
                h2=mod(h2-d,m2);
                h1=mod(h1*inv1,m1);
                h2=mod(h2*inv2,m2);
            }
        }
        ans*=2*n;
        ans%=m;
        for(int i = 1 ; n>=i ; i++)
        {
            pr[i].clear();
            pr[i].pb(0);    
            h1 = suf1[i][1];
            h2 = suf2[i][1];
            for(int j = 1 ; a[i].size()>j ; j++)
            {
                pr[i].pb(mp[{h1,h2}]);
                o=mod(o+pr[i][j]*(a[i].size()-j),m);
                d = a[i][j];
                h1=mod(h1-d,m1);
                h2=mod(h2-d,m2);
                h1=mod(h1*inv1,m1);
                h2=mod(h2*inv2,m2);
            }
        }
        for(auto it : v2)
        {
            ll sz = a[it].size()-1;
            ll szz;
            bool g;
            for(int i = 1 ; n>=i ; i++)
            {
                g=0;
                szz = a[i].size()-1;
                mn = min(sz,szz);
                do
                {
                    fh1=suf1[it][sz-mn+1];
                    fh2=suf2[it][sz-mn+1];
                    sh1=pre1[i][mn];
                    sh2=pre2[i][mn];
                    if(fh1==sh1&&fh2==sh2)
                    {
                        if(g)
                            o=mod(o-mn,m);
                        g=1;
                    }
                }
                while(--mn);
            }
        }
        for(auto it : v1)
        {
            for(int i = 1 ; a[it].size()>i ; i++)
            {
                fh1 = suf1[it][i];
                fh2 = suf2[it][i];
                ll id = a[it].size()-1;
                pe1 = fp(p1,a[it].size()-i-1,m1);
                pe2 = fp(p2,a[it].size()-i-1,m2);
                ll sz = a[it].size()-i;
                for(int j = i+1 ; a[it].size()>j ; j++)
                {
                    sz--;
                    sh1=suf1[it][j];
                    sh2=suf2[it][j];
                    ll d = a[it][id];
                    id--;
                    fh1 = mod(fh1 - pe1*d,m1);
                    fh2 = mod(fh2 - pe2*d,m2);
                    pe1=mod(pe1*inv1,m1);
                    pe2=mod(pe2*inv2,m2);
                    if(fh1==sh1&&fh2==sh2)
                    {
                        pr[it][j]-=pr[it][i];
                        o=mod(o-pr[it][i]*sz,m);
                    }
                }
            }
        }
        ans=mod(ans-o,m);
        ans=mod(ans*fp(mod(n*n,m),m-2,m),m);
        cans
    }
}