Arrays Connection#12304
Problem Author: | De3b0o |
Prepared by: | De3b0o |
Edited by: | Hasan Saleh (MathModel) |
Solution
Let's define ov(i,j) as the maximum overlap between arrays and (The length of the longest suffix of array that's also a prefix of array ) and as the sum of sizes of all arrays.
We can see that the size of the connection of arrays and is equal to sz_i + sz_j + ov(i,j).
So the expected size of the connection of two random arrays is equal to:
\frac{\sum_{i=1}^{n} \sum_{j=1}^{n} sz_i + sz_j + ov(i,j)}{n^2} Which is equal to \frac{2n \cdot m + \sum_{i=1}^{n} \sum_{j=1}^{n} ov(i,j)}{n^2}
Now to calculate \sum_{i=1}^{n} \sum_{j=1}^{n} ov(i,j):
We can for each suffix of every array , count how many arrays have this suffix as a prefix using hashing.
And to remove over counting (because arrays and can overlap at multiple points and we only care about the one with maximum length) for each we do one of the following approaches based on the size of the array .
Approach (sz_i \le \sqrt m):
For all suffixes (1 \le s1 < s2 \le n) where suffix means all elements from up to sz_i.
If the first sz_i - s2 +1 elements of suffix are equal to suffix then all arrays that overlap with array at point (arrays that have the suffix as a prefix) also overlap at point .
We can check in O(1) using hashing.
And since we already know how many arrays overlap at point we subtract the number from the number of arrays that overlap at point to get rid of the over counting.
Approach (sz_i > \sqrt m):
Since there can only be at most \sqrt m that satisfy this condition, we can for each one, iterate over all prefixes of all arrays and check if they overlap here.
Complexity \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
}
}