Permutation de Sous-tableaux et Requêtes #12256

Permutation de Sous-tableaux et Requêtes (Corrigé)

Auteur du problème:	Hasan Saleh (MathModel)
Préparé par:	Hasan Saleh (MathModel)
Édité par:	Hasan Saleh (MathModel)

Solution

Soit $a$ un multiset de taille $n$ , avec la somme des valeurs $S = \sum a_{i}$ S=\sum a_i, et soit $c_{x}$ c_x la multiplicité de la valeur $x$ dans $a$ .

Pour une permutation fixe et une position $p$ ( $1 \leq p \leq n$ 1\le p\le n), le coefficient de l'élément placé à $p$ dans la somme de tous les sous-tableaux est égal à

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

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

En effet, il y a $p$ choix pour l'extrémité gauche et $(n - p + 1)$ (n-p+1) pour l'extrémité droite qui incluent $p$ .

En sommant sur les positions et ensuite sur les permutations : - Le nombre de permutations distinctes d'un multiset est $\frac{n !}{\prod _{x} c _{x} !}$ \dfrac{n!}{\prod_x c_x!}. - Par symétrie à travers les permutations distinctes, la valeur moyenne à n'importe quelle position est $S / n$ . - Ainsi, le facteur de contribution total de $S$ est égal à

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

Une identité standard donne

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

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

Par conséquent, pour $n \geq 1$ n\ge 1,

R e ˊ ponse = \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{Réponse} = \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!}\;}

et pour $n = 0$ n=0, la réponse est $0$ .

Nous devons donc seulement maintenir, après chaque requête : - $n$ (taille actuelle), - $S$ (somme actuelle 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.

Les mises à jour sont $O (1)$ : - En insérant $x$ : soit $t = c_{x}$ t=c_x avant l'insertion, alors $c_{x} \leftarrow t + 1$ c_x\!\leftarrow\! t+1 et

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

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

- En supprimant $x$ : soit $t = c_{x}$ t=c_x avant la suppression, alors $c_{x} \leftarrow t - 1$ c_x\!\leftarrow\! t-1 et

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

D \leftarrow D\cdot t\pmod M .

Nous précomputons $!$ et les inverses modulaires jusqu'à $2 \cdot 1 0^{6}$ 2\cdot 10^6 (puisque $\sum (n + q) \leq 2 \cdot 1 0^{6}$ \sum(n+q)\le 2\cdot 10^6), et nous avons également besoin de $6^{- 1} mod M$ 6^{-1}\bmod M pour obtenir $(3 n + 2) = \frac{n ( n + 1 ) ( n + 2 )}{6}$ \binom{n+2}{3}=\dfrac{n(n+1)(n+2)}{6}.

Réponse à chaque étape (pour $n > 0$ n>0) :

R e ˊ ponse \equiv (n - 1)! \cdot (3 n + 2) \cdot S \cdot D (mod M) .

\text{Réponse} \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++