Перестановка підмасивів та запити #12256

Перестановка підмасивів та запити (Розбір)

Автор проблеми:	Хасан Салех (MathModel)
Підготовлено:	Хасан Салех (MathModel)
Редаговано:	Хасан Салех (MathModel)

Рішення

Нехай $a$ буде мультимножиною розміру $n$ , з сумою значень $S = \sum a_{i}$ S=\sum a_i, і нехай $c_{x}$ c_x буде кратність значення $x$ в $a$ .

Для фіксованої перестановки та позиції $p$ ( $1 \leq p \leq n$ 1\le p\le n), коефіцієнт елемента, розміщеного на $p$ в сумі всіх підмасивів дорівнює

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

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

Дійсно, є $p$ виборів для лівого кінця і $(n - p + 1)$ (n-p+1) для правого кінця, які включають $p$ .

Сумуючи по позиціях, а потім по перестановкам: - Кількість різних перестановок мультимножини дорівнює $\frac{n !}{\prod _{x} c _{x} !}$ \dfrac{n!}{\prod_x c_x!}. - За симетрією через різні перестановки, середнє значення на будь-якій позиції дорівнює $S / n$ . - Отже, загальний внесок фактора $S$ дорівнює

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

Стандартна ідентичність дає

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

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

Отже, для $n \geq 1$ n\ge 1,

Відповідь = \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{Відповідь} = \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!}\;}

а для $n = 0$ n=0 відповідь дорівнює $0$ .

Отже, нам потрібно лише підтримувати, після кожного запиту: - $n$ (поточний розмір), - $S$ (поточна сума за модулем $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.

Оновлення є $O (1)$ : - При вставці $x$ : нехай $t = c_{x}$ t=c_x перед вставкою, тоді $c_{x} \leftarrow t + 1$ c_x\!\leftarrow\! t+1 і

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

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

- При видаленні $x$ : нехай $t = c_{x}$ t=c_x перед видаленням, тоді $c_{x} \leftarrow t - 1$ c_x\!\leftarrow\! t-1 і

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

D \leftarrow D\cdot t\pmod M .

Ми попередньо обчислюємо $!$ та модульні обернені значення до $2 \cdot 1 0^{6}$ 2\cdot 10^6 (оскільки $\sum (n + q) \leq 2 \cdot 1 0^{6}$ \sum(n+q)\le 2\cdot 10^6), а також потрібно $6^{- 1} mod M$ 6^{-1}\bmod M, щоб отримати $(3 n + 2) = \frac{n ( n + 1 ) ( n + 2 )}{6}$ \binom{n+2}{3}=\dfrac{n(n+1)(n+2)}{6}.

Відповідь на кожному кроці (для $n > 0$ n>0):

Відповідь \equiv (n - 1)! \cdot (3 n + 2) \cdot S \cdot D (mod M) .

\text{Відповідь} \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++