Thứ Sáu, 4 tháng 1, 2019

Codeforces Round 57- Bài 6

Bài 6: A permutation of size $n$ is an array of size $n$ such that each integer from $1$ to $n$ occurs exactly once in this array. An inversion in a permutation $p$ is a pair of indices $(i,j)$ such that $i>j$ and $a_i,a_j$. For example, a permutation $[4,1,3,2]$ contains $4$ inversion: $(2,1),(3,1),(4,1),(4,3)$.
You are given a permutation $p$ of size $n$. However, the numbers on some positions are replaced by $-1$. Let the valid permutation be such a replacement of $-1$ in this sequence back to numbers from $1$ to $n$ in such a way that the resulting sequence is a permutation of size $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 $\frac{P}{Q}$ where $P$ ans $Q$ are non-negative integers and $Q\ne 0$. Report the value of $P.Q^{-1}(\text{ mod }998244353)$.
Input
The first line contains a single integer $n(1\le n\le 2.10^5)$- the length of the sequence.
The second line contains $n$ integers $p_1,p_2,...,p_n(-1\le p_i\le n,p_i\ne 0)$- the initial sequence.
It is guaranteed that all elements not equal to $-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 $\frac{P}{Q}$ where $P$ and $Q$ are non-negative integers and $Q\ne 0$. Report the value of $P.Q^{-1}(\text{ mod }998244353)$.
Examples
input
Copy
3
3 -1 -1
output
Copy
499122179
input
Copy
2
1 2
output
Copy
0
input
Copy
2
-1 -1
output
Copy
499122177
 Solution:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200005,M=998244353;
int num[N],a[N],flag[N],g[N],n,f[N];
void insert(int x){
 for (;x;x-=x&-x)num[x]++;
}
int find(int x){
 int ans=0;
 for (;x<=n;x+=x&-x)ans+=num[x];
 return ans;
}
int ksm(int x,int y){
 if (!y)return 1;
 int z=ksm(x,y/2);
 z*=z;z%=M;
 if (y&1)z*=x;
 return z%M;
}
signed main(){
 scanf("%lld",&n);
 for (int i=1;i<=n;i++)scanf("%lld",&a[i]),flag[a[i]]=1;
 for (int i=n;i;i--){
  f[i]=f[i+1];
  if (a[i]==-1)f[i]++;
  g[i]=g[i+1];
  if (!flag[i])g[i]++;
 }
 int ans=f[1]*(f[1]-1)%M*ksm(4,M-2)%M;
 for (int i=1;i<=n;i++)
  if (a[i]!=-1){
   ans+=find(a[i]);
   insert(a[i]);
   (ans+=(f[1]-g[a[i]])*f[i]%M*ksm(f[1],M-2)+g[a[i]]*(f[1]-f[i])%M*ksm(f[1],M-2))%=M;
  }
 printf("%lld",ans); 
 return 0; 
}

Không có nhận xét nào:

Đăng nhận xét

Bài G - Educatioal Round 62

Đề bài: Bạn được cho 1 đồ thị vô hướng đặc biệt. Nó bao gồm $2n$ đỉnh được đánh số từ 1 đến 2n. Dưới đây là một số đặc tính của đồ thị: + ...