Permutation of Subarrays and Queries #12256

Permutation of Subarrays and Queries (Editorial)

Problem Author:	Hasan Saleh (MathModel)
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution

Let $a$ be a multiset of size $n$ , with value-sum $S = \sum a_{i}$ S=\sum a_i, and let $c_{x}$ c_x be the multiplicity of value $x$ in $a$ .

For a fixed permutation and position $p$ ( $1 \leq p \leq n$ 1\le p\le n), the coefficient of the element placed at $p$ in the sum of all subarrays equals

w_{p} = p (n - p + 1) .

w_p \;=\; p\,(n-p+1).

Indeed, there are $p$ choices for the left end and $(n - p + 1)$ (n-p+1) for the right end that include $p$ .

Summing over positions and then over permutations: - The number of distinct permutations of a multiset is $\frac{n !}{\prod _{x} c _{x} !}$ \dfrac{n!}{\prod_x c_x!}. - By symmetry across distinct permutations, the average value at any position is $S / n$ . - Hence the total contribution factor of $S$ equals

\frac{n !}{\prod _{x} c _{x} !} \cdot \frac{1}{n} \cdot p = 1 \sum n w_{p} = \frac{n !}{\prod _{x} c _{x} !} \cdot \frac{1}{n} \cdot p = 1 \sum n p (n - p + 1) .

\frac{n!}{\prod_x c_x!}\cdot \frac{1}{n}\cdot \sum_{p=1}^n w_p \;=\; \frac{n!}{\prod_x c_x!}\cdot \frac{1}{n}\cdot \sum_{p=1}^n p(n-p+1).

A standard identity gives

p = 1 \sum n p (n - p + 1) = (3 n + 2) .

\sum_{p=1}^n p(n-p+1) \;=\; \binom{n+2}{3}.

Therefore, for $n \geq 1$ n\ge 1,

Ans = \frac{n !}{\prod _{x} c _{x} !} \cdot \frac{1}{n} \cdot (3 n + 2) \cdot S = (n - 1)! \cdot (3 n + 2) \cdot \frac{S}{\prod _{x} c _{x} !}

\boxed{\;\text{Ans} = \frac{n!}{\prod_x c_x!}\cdot \frac{1}{n}\cdot \binom{n+2}{3}\cdot S = (n-1)!\cdot \binom{n+2}{3}\cdot \frac{S}{\prod_x c_x!}\;}

and for $n = 0$ n=0 the answer is $0$ .

So we only need to maintain, after each query: - $n$ (current size), - $S$ (current sum modulo $M = 1 0^{9} + 7$ M=10^9+7), - $D = (\prod_{x} c_{x}!)^{- 1} (mod M)$ D=\left(\prod_x c_x!\right)^{-1}\pmod M.

Updates are $O (1)$ : - On inserting $x$ : let $t = c_{x}$ t=c_x before the insert, then $c_{x} \leftarrow t + 1$ c_x\!\leftarrow\! t+1 and

D \leftarrow D \cdot (t + 1)^{- 1} (mod M) .

D \leftarrow D\cdot (t+1)^{-1}\pmod M .

- On removing $x$ : let $t = c_{x}$ t=c_x before the removal, then $c_{x} \leftarrow t - 1$ c_x\!\leftarrow\! t-1 and

D \leftarrow D \cdot t (mod M) .

D \leftarrow D\cdot t\pmod M .

We precompute $!$ and modular inverses up to $2 \cdot 1 0^{6}$ 2\cdot 10^6 (since $\sum (n + q) \leq 2 \cdot 1 0^{6}$ \sum(n+q)\le 2\cdot 10^6), and also need $6^{- 1} mod M$ 6^{-1}\bmod M to get $(3 n + 2) = \frac{n ( n + 1 ) ( n + 2 )}{6}$ \binom{n+2}{3}=\dfrac{n(n+1)(n+2)}{6}.

Answer at each step (for $n > 0$ n>0):

Ans \equiv (n - 1)! \cdot (3 n + 2) \cdot S \cdot D (mod M) .

\text{Ans} \equiv (n-1)!\ \cdot\ \binom{n+2}{3}\ \cdot\ S\ \cdot\ D \pmod M.

#include <bits/stdc++.h>

using namespace std;
using ll=long long;
const int M=1e9+7;
#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

int f[2000005],inv[2000005];

int fpow(int a,ll e){
    ll r=1;
    while(e){
        if(e&1)r=r*a%M;
        a=1LL*a*a%M;
        e>>=1;
    }
    return (int)r;
}

int mul(int a,int b){ return (int)(1LL*a*b%M); }

int W(int n,int w6){ 
    return mul(mul((int)(1LL*n*(n+1)%M),(n+2)%M),w6);
}

int calc(int n,int den,ll S,int w6){
    if(!n) return 0;
    return mul(mul(f[n-1],den),mul(W(n,w6),(S%M+M)%M));
}

void solve(){
    int n,q; cin>>n>>q;
    f[0]=1;
    for(int i=1;i<=2000000;i++)f[i]=mul(f[i-1],i);
    inv[2000000]=fpow(f[2000000],M-2);
    for(int i=2000000;i;i--)inv[i-1]=mul(inv[i],i);
    int w6=fpow(6,M-2);

    unordered_map<ll,int> mp;
    ll S=0;
    int den=1;

    for(int i=0;i<n;i++){
        ll x; cin>>x;
        S+=x;
        int t=mp[x]++;                 
        den=mul(den, mul(f[t],inv[t+1]));
    }

    cout<<calc(n,den,S,w6)<<' ';
    while(q--){
        char c; ll x; cin>>c>>x;
        if(c=='+'){
            S+=x;
            int t=mp[x]++;
            den=mul(den, mul(f[t],inv[t+1])); 
            n++;
        }else{
            S-=x;
            int t=mp[x]--;                    
            den=mul(den, t);                 
            if(mp[x]==0) mp.erase(x);
            n--;
        }
        cout<<calc(n,den,S,w6)<<' ';
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    while(T--)solve();
}

C++