Altmassivlərin Permutasiyaları və Sorğular#12256

Altmassivlərin Permutasiyaları və Sorğular (Həll təhlili)

Problemin Müəllifi:	Hasan Saleh (MathModel)
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll

$a$ -nı ölçüsü $n$ olan bir çoxluq, dəyər cəmi $S = \sum a_{i}$ S=\sum a_i və $c_{x}$ c_x-i $a$ -da dəyər $x$ -in çoxluğunu göstərən bir çoxluq olaraq qəbul edək.

Müəyyən bir permutasiya və mövqe $p$ ( $1 \leq p \leq n$ 1\le p\le n) üçün, $p$ -də yerləşdirilən elementin bütün altmassivlərin cəmi içindəki koeffisiyenti bərabərdir

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

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

Həqiqətən, $p$ üçün sol ucu seçmək üçün $p$ seçim var və $p$ -ni daxil edən sağ ucu seçmək üçün $(n - p + 1)$ (n-p+1) seçim var.

Mövqe üzrə cəmləmə və sonra permutasiyalar üzrə cəmləmə: - Bir çoxluğun fərqli permutasiyalarının sayı $\frac{n !}{\prod _{x} c _{x} !}$ \dfrac{n!}{\prod_x c_x!}-dir. - Fərqli permutasiyalar arasında simmetriya ilə, hər mövqedə orta dəyər $S / n$ -dir. - Beləliklə, $S$ -nin ümumi töhfə faktoru bərabərdir

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

Standart bir identiklik verir

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

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

Buna görə, $n \geq 1$ n\ge 1 üçün,

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

və $n = 0$ n=0 üçün cavab $0$ -dır.

Beləliklə, hər sorğudan sonra yalnız aşağıdakılara nəzarət etməliyik: - $n$ (hazırkı ölçü), - $S$ (hazırkı cəm modulu $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.

Yeniləmələr $O (1)$ -dir: - $x$ əlavə edərkən: $t = c_{x}$ t=c_x əlavə etmədən əvvəl, $c_{x} \leftarrow t + 1$ c_x\!\leftarrow\! t+1 və

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

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

- $x$ silərkən: $t = c_{x}$ t=c_x silməzdən əvvəl, $c_{x} \leftarrow t - 1$ c_x\!\leftarrow\! t-1 və

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

D \leftarrow D\cdot t\pmod M .

Biz $!$ və modul tərsini $2 \cdot 1 0^{6}$ 2\cdot 10^6-a qədər əvvəlcədən hesablayırıq (çünki $\sum (n + q) \leq 2 \cdot 1 0^{6}$ \sum(n+q)\le 2\cdot 10^6), həmçinin $(3 n + 2) = \frac{n ( n + 1 ) ( n + 2 )}{6}$ \binom{n+2}{3}=\dfrac{n(n+1)(n+2)}{6}-nı əldə etmək üçün $6^{- 1} mod M$ 6^{-1}\bmod M-ə ehtiyacımız var.

Hər addımda cavab (üçün $n > 0$ n>0):

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

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