[codeforces1096F]Inversion Expectation

22080 단어 데이터 구조트 리 배열
time limit per test : 2 seconds memory limit per test : 256 megabytes
A permutation of size n n n is an array of size n n n such that each integer from 1 1 1 to n n n occurs exactly once in this array. An inversion in a permutation p p p is a pair of indices ( i , j ) (i,j) (i,j) such that i > j i>j i>j and a i < a j a_iYou are given a permutation p p p of size n n n. However, the numbers on some positions are replaced by − 1 −1 −1. Let the valid permutation be such a replacement of − 1 −1 −1 in this sequence back to numbers from 1 1 1 to n n n in such a way that the resulting sequence is a permutation of size n n n.
The given sequence was turned into a valid permutation randomly with the equal probability of getting each valid permutation.
Calculate the expected total number of inversions in the resulting valid permutation.
It can be shown that it is in the form of P ∗ Q − 1 P*Q^{-1} P∗Q−1 where P P P and Q are non-negative integers and Q≠0. Report the value of P ⋅ Q − 1 P⋅Q^{−1} P⋅Q−1( m o d mod mod 998244353 998244353 998244353).
Input
The first line contains a single integer n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 ) n(1≤n≤2⋅10^5) n(1≤n≤2⋅105) — the length of the sequence.The second line contains n n n integers p 1 , p 2 , … , p n ( − 1 ≤ p i ≤ n , p i ≠ 0 ) p_1,p_2,…,p_n (−1≤p_i≤n, pi≠0) p1​,p2​,…,pn​(−1≤pi​≤n,pi̸​=0) — the initial sequence. It is guaranteed that all elements not equal to − 1 −1 −1 are pairwise distinct.
Output
Print a single integer — the expected total number of inversions in the resulting valid permutation. It can be shown that it is in the form of P ∗ Q − 1 P*Q^{-1} P∗Q−1 where P P P and Q Q Q are non-negative integers and Q Q Q ≠ 0 0 0. Report the value of P ⋅ Q − 1 P⋅Q^{−1} P⋅Q−1( m o d mod mod 998244353 998244353 998244353). Examples Input 
3
3 -1 -1

Output 
499122179

Input 
2
1 2

Output 
0

Input 
2
-1 -1

Output 
499122177

Note
In the first example two resulting valid permutations are possible: [ 3 , 1 , 2 ] — 2 [3,1,2]— 2 [3,1,2]—2 inversions; [ 3 , 2 , 1 ] — 3 [3,2,1]— 3 [3,2,1]—3 inversions. The expected value is 2 ⋅ 1 + 3 ⋅ ( 1 / 2 ) = 2.5 2⋅1+3⋅(1/2)=2.5 2⋅1+3⋅(1/2)=2.5. In the second example no − 1 −1 −1 are present, thus the only valid permutation is possible — the given one. It has 0 0 0 inversions. In the third example there are two resulting valid permutations — one with 0 0 0 inversions and one with 1 1 1 inversion.
제목: 길이 n n n 의 배열 을 주 고 일부 위 치 는 - 1 - 1 - 1 - 1 - 1 로 불확실 하 다 는 뜻 으로 이 서열 의 역순 대수 에 대한 기 대 를 구한다.
문제 풀이: 이 몇 가지 상황 으로 나 누 어 토론 한다.
1: 만약 두 숫자 가 모두 확실 하지 않다 면, 분명히 답 에 대한 공헌 은 1 / 2 1 / 2 1 / 2
2: i < j i < j i < j 및 a [i] = = − 1 a [i] = - 1 a [i] = = − 1 및 a [j]! = − 1 a [j]! = - 1 a [j]!왼쪽 에 몇 개의 불확실 한 위치 가 있 습 니 다. s u m j sum j sumj 는 불확실 한 숫자 중 a [j] a [j] a [j] 보다 작은 것 을 표시 합 니 다.
3: i > j i > j i > j 및 a [i] = = − 1 a [i] = - 1 a [i] = = − 1 및 a [j]! = − 1 a [j]! = - 1 a [j]!왼쪽 에 몇 개의 불확실 한 위치 가 있 는데 s u m t j sumt j sumtj 는 불확실 한 숫자 중 a [j] a [j] a [j] a [j] 보다 크다 는 것 을 나타 낸다.
4: 두 숫자 가 모두 확실 하 다 면 바로 계산 하면 됩 니 다.
이 네 가지 상황 을 각각 계산 하면 된다.
#include
#define LiangJiaJun main
#define MOD 998244353LL
#define ll long long
using namespace std;
inline int lowbit(int x){return x&(-x);}
ll fp(ll x,ll y){
    if(y==0)return 1;
    ll temp=fp(x,y>>1);
    if(y&1){
        return (((temp*temp)%MOD)*x)%MOD;
    }
    else return (temp*temp)%MOD;
}
ll rev(ll x){
    return fp(x,MOD-2);
}


int n,a[200004];
int tr[200004],c[200004];
ll rev4,revc,ans,sum;
void add(int x){
    for(int i=x;i<=n;i+=lowbit(i))tr[i]++;
}
int query(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i))res+=tr[i];
    return res;
}
int goc(int x){
    return x-query(x);
}
int LiangJiaJun(){
    scanf("%d",&n);
    c[0]=0;
    sum=0;
    ans=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum+=(a[i]!=-1);
        if(a[i]!=-1)add(a[i]);
        c[i]=c[i-1]+(a[i]==-1);
    }
    rev4=rev(4);
    revc=rev(c[n]);
    ans=((1LL*(c[n])*(c[n]-1))%MOD);
    ans=(ans*rev4)%MOD;
    for(int i=1;i<=n;i++){
        if(a[i]!=-1){
            ll now=n-sum-goc(a[i]);
            now=(now*c[i])%MOD;
            now=(now*revc)%MOD;
            ans=(ans+now)%MOD;
            now=goc(a[i]);
            now=(now*(c[n]-c[i]))%MOD;
            now=(now*revc)%MOD;
            ans=(ans+now)%MOD;
        }
    }
    memset(tr,0,sizeof(tr));
    int kac=0;
    for(int i=1;i<=n;i++){
        if(a[i]==-1)continue;
        ans+=kac-query(a[i]);
        kac++;
        add(a[i]);
    }
    printf("%lld
",(ans+MOD)%MOD);
    return 0;
}
Codeforce 383C. Propagating tree
Codeforces 754 D Fedor and coupons

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage