Array-ların Bağlantısı#12304

Array-ların Bağlantısı (Həll təhlili)

Problem Müəllifi:	De3b0o
Hazırlayan:	De3b0o
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Gəlin $o v (i, j)$ ov(i,j)-ni massivlər $i$ və $j$ arasında maksimum örtüşmə kimi təyin edək (massiv $i$ -nin ən uzun suffixinin massiv $j$ -nin prefixi olduğu uzunluq) və $m$ -ni bütün massivlərin ölçülərinin cəmi kimi təyin edək.

Görürük ki, massivlər $i$ və $j$ -nin birləşməsinin ölçüsü $s z_{i} + s z_{j} + o v (i, j)$ sz_i + sz_j + ov(i,j)-ə bərabərdir.

Beləliklə, iki təsadüfi massivlərin birləşməsinin gözlənilən ölçüsü:

$\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} Bu, bərabərdir $\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}

İndi $\sum_{i = 1}^{n} \sum_{j = 1}^{n} o v (i, j)$ \sum_{i=1}^{n} \sum_{j=1}^{n} ov(i,j)-ni hesablamaq üçün:

Hər bir massiv $i$ -nin hər bir suffixi üçün, bu suffixi prefix olaraq qəbul edən neçə massiv $j$ olduğunu saymaq olar.

Və üst-üstə saymağı aradan qaldırmaq üçün (çünki massivlər $i$ və $j$ bir neçə nöqtədə örtüşə bilər və biz yalnız maksimum uzunluğa malik olanı nəzərə alırıq) hər $i$ üçün massiv $i$ -nin ölçüsünə əsaslanaraq aşağıdakı yanaşmalardan birini tətbiq edirik.

Yanaşma $1$ ( $s z_{i} \leq m$ sz_i \le \sqrt m):

Bütün suffixlər $s 1, s 2$ ( $1 \leq s 1 < s 2 \leq n$ 1 \le s1 < s2 \le n) üçün, burada suffix $j$ $j$ -dən $s z_{i}$ sz_i-yə qədər olan bütün elementləri ifadə edir.

Əgər suffix $s 1$ -in ilk $s z_{i} - s 2 + 1$ sz_i - s2 +1 elementi suffix $s 2$ -yə bərabərdirsə, onda massiv $i$ -lə $s 1$ nöqtəsində örtüşən bütün massivlər (suffix $s 1$ -i prefix olaraq qəbul edən massivlər) də $s 2$ nöqtəsində örtüşür.

Bunu O(1) ilə hashing istifadə edərək yoxlaya bilərik.

Və artıq $s 1$ nöqtəsində neçə massiv $j$ -nin örtüşdüyünü bildiyimiz üçün, $s 2$ nöqtəsində örtüşən massivlərin sayından bu sayını çıxırıq ki, üst-üstə saymanı aradan qaldıraq.

Yanaşma $2$ ( $s z_{i} > m$ sz_i > \sqrt m):

Bu şərti ödəyən ən çox $m$ \sqrt m ola biləcəyinə görə, hər biri üçün bütün massivlərin prefixləri arasında dövr edə bilərik və burada örtüşüb-örtüşmədiyini yoxlaya bilərik.

Komplekslik $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 << "BƏLİ" << "\n";
#define no cout << "XƏTA" << "\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
    }
}