¡Permutación de Subarreglos y Consultas#12256

¡Permutación de Subarreglos y Consultas (Editorial)

Autor del Problema:	Hasan Saleh (MathModel)
Preparado por:	Hasan Saleh (MathModel)
Editado por:	Hasan Saleh (MathModel)

Solución

Sea $a$ un multiconjunto de tamaño $n$ , con suma de valores $S = \sum a_{i}$ S=\sum a_i, y sea $c_{x}$ c_x la multiplicidad del valor $x$ en $a$ .

Para una permutación fija y posición $p$ ( $1 \leq p \leq n$ 1\le p\le n), el coeficiente del elemento colocado en $p$ en la suma de todos los subarreglos es igual a

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

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

De hecho, hay $p$ elecciones para el extremo izquierdo y $(n - p + 1)$ (n-p+1) para el extremo derecho que incluyen $p$ .

Sumando sobre posiciones y luego sobre permutaciones: - El número de permutaciones distintas de un multiconjunto es $\frac{n !}{\prod _{x} c _{x} !}$ \dfrac{n!}{\prod_x c_x!}. - Por simetría a través de permutaciones distintas, el valor promedio en cualquier posición es $S / n$ . - Por lo tanto, el factor de contribución total de $S$ es

\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).

Una identidad estándar da

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

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

Por lo tanto, para $n \geq 1$ n\ge 1,

Respuesta = \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{Respuesta} = \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!}\;}

y para $n = 0$ n=0 la respuesta es $0$ .

Así que solo necesitamos mantener, después de cada consulta: - $n$ (tamaño actual), - $S$ (suma actual módulo $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.

Las actualizaciones son $O (1)$ : - Al insertar $x$ : sea $t = c_{x}$ t=c_x antes de la inserción, entonces $c_{x} \leftarrow t + 1$ c_x\!\leftarrow\! t+1 y

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

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

- Al eliminar $x$ : sea $t = c_{x}$ t=c_x antes de la eliminación, entonces $c_{x} \leftarrow t - 1$ c_x\!\leftarrow\! t-1 y

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

D \leftarrow D\cdot t\pmod M .

Precomputamos $!$ y las inversas modulares hasta $2 \cdot 1 0^{6}$ 2\cdot 10^6 (ya que $\sum (n + q) \leq 2 \cdot 1 0^{6}$ \sum(n+q)\le 2\cdot 10^6), y también necesitamos $6^{- 1} mod M$ 6^{-1}\bmod M para obtener $(3 n + 2) = \frac{n ( n + 1 ) ( n + 2 )}{6}$ \binom{n+2}{3}=\dfrac{n(n+1)(n+2)}{6}.

Respuesta en cada paso (para $n > 0$ n>0):

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

\text{Respuesta} \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++