Codeforces 1096F(dp + 树状数组)

题意：

对于长度为$n$的排列，在已知一些位的前提下求逆序对的期望

思路：

将答案分为$3$部分

$1.$$-1$与$-1$之间对答案的贡献。由于逆序对考虑的是数字之间的大小关系，故假设$-1$的数量为$cnt$，可以等效成求长度为$cnt$的排列的逆序对期望。设$dp[i]$为长度为$i$的全排列的逆序对期望，有$dp[i]=dp[i-1]+$$\frac{i-1}{2}$，可以理解成在原$dp[i-1]$的基础上，数值$i$对每个长度为$i-1$的排列产生$\sum_{t=1}^{i-1}t$个逆序对，共有$(i-1)!$个排列，所以期望为$\frac{(i-1)!*i*(i-1)}{(2*i!)}$$=\frac{i-1}{2}$，移项后使用累加法可以求出通项为$dp[i]=$$\frac{i*(i-1)}{4}$。

$2.$非$-1$之间对答案的贡献。可以将出现概率看作$1$，所以贡献就是逆序对数量，用树状数组求。

$3.$$-1$与非$-1$之间的贡献。设共有$cnt$个$-1$，考虑每个$a[i]$$\neq$$-1$，设这个$a[i]$它前边$-1$的数量为$nop$，它大的未填的数的数量为$high[a[i]]$，那么$a[i]$对这部分答案的贡献为$\frac{nop*high[a[i]]*(cnt-1)!}{cnt!}$$=$$\frac{nop*high[a[i]]}{cnt}$。比$a[i]$小的数与$a[i]$后边的$-1$构成类似的关系。

代码：

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <map>

#include <set>

#include <cmath>

#include <queue>

#include <stack>

#include <cstdio>

#include <vector>

#include <cassert>

#include <cstring>

#include <iostream>

#include <algorithm>

#define IOS    ios::sync_with_stdio(0),cin.tie(0);

#define DBG(x) cerr << #x << " = " << x << endl;	

#define PII pair<int,int>

#define FI  first

#define SE  second

using namespace std;

typedef long long LL;

typedef long double LD;

typedef unsigned long long ULL;

const int inf = 0x3f3f3f3f;

const int mod = 998244353;

const double eps = 1e-8;

const double pi  = acos(-1.0);

void file(){

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

}

namespace BakuretsuMahou{

	const int N = 2e5 + 5;

	const int inv2 = (mod + 1) / 2;

	int n, a[N], vis[N];

	int high[N], low[N];

	int pre[N], cnt;

	LL ans, fac[N];

	LL add(LL a, LL b){

		return (a+b)%mod;

	}

	LL mul(LL a, LL b){

		return (a*b)%mod;

	}

	struct BIT{

		int c[N];

		int lowbit(int x){

			return (x)&(-x);

		}

		void update(int x, int y){

			while(x <= n){

				c[x] += y;

				x += lowbit(x);

			}

		}

		LL query(int x){

			LL res = 0;

			while(x >= 1){

				res += c[x];

				x -= lowbit(x);

			}

			return res;

		}

	}tree;

	LL qpow(LL a, LL b, LL p){

		LL res = 1;

		while(b){

			if(b&1)res = mul(res, a);

			a = mul(a, a);

			b >>= 1;

		}

		return res;

	}

	LL Fermat(LL a, LL p){

		return qpow(a, p - 2, p);

	}

	LL dp(LL x){

		return mul(mul(x, x - 1), Fermat(4, mod));

	}

	void init(){

		fac[0] = 1;

		for(int i = 1; i < N; i++){

			fac[i] = mul(fac[i - 1], i);

		}

	}

	void Explosion(){

		init();

		scanf("%d", &n);

		for(int i = 1; i <= n; i++){

			scanf("%d", &a[i]);

			if(a[i] != -1){

				vis[a[i]] = 1;

				ans = add(ans, i - 1 - cnt - tree.query(a[i]));

				tree.update(a[i], 1);

			}else cnt++, pre[i]++;

			pre[i] += pre[i - 1];

		}

		ans = add(ans, dp(cnt));

		LL inv = Fermat(cnt, mod);

		for(int i = 2; i <= n; i++)low[i] = low[i - 1] + (vis[i - 1] ^ 1);

		for(int i = n - 1; i >= 1; i--)high[i] = high[i + 1] + (vis[i + 1] ^ 1);

		for(int i = 1; i <= n; i++){

			if(a[i] != -1){

				LL nop = pre[i], nos = pre[n] - pre[i];

				ans = add(ans, mul(mul(nos, low[a[i]]), inv));

				ans = add(ans, mul(mul(nop, high[a[i]]), inv));

			}

		}

		printf("%I64d\n", ans);

	}

}

int main(){

	//IOS

	//file();

	BakuretsuMahou::Explosion();

	return 0;

}

巴特西

Codeforces 1096F(dp + 树状数组)

最新文章

热门文章