树状数组+概率论，ABC380G - Another Shuffle Window

ops/2024/11/17 22:07:20/

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

G - Another Shuffle Window

二、解题报告

1、思路分析

不难用树状数组计算全局逆序对tot

我们可以在滑窗过程中维护当前 k-子数组的逆序对数目cur（不计入滑窗内的数和滑窗外的数字构成的逆序对）

对于滑窗的每个时刻，滑窗外元素对逆序对的贡献为 tot - cur

也就是说，每个滑窗，不带滑窗内会有tot - cur个逆序对

每个滑窗这一部分的贡献为 (tot - cur) * (n - k + 1)，因为 n - k + 1个滑窗等概率，所以贡献比例相同，这一部分的答案我们滑窗过程中直接累加

关键在于如何理解滑窗内元素之间的逆序对数目？

我们发现我们只需计算子数组内产生的逆序对，而对于一个数组而言，数组内任意两个数之间构成逆序对的数目为 1 / 2，而 k-数组 pair 的数目为 k * (k - 1) / 2，每个pair 贡献1个逆序对的概率为1/2，根据二项分布的数学期望计算公式：E = np可得，k-数组的逆序对贡献期望为 k * (k - 1) / 4

那么答案就是把两部分加起来，详细看代码

2、复杂度

时间复杂度： O(NlogN)空间复杂度：O(N)

3、代码详解

 ​
#include <bits/stdc++.h>// #define DEBUGusing u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;template<class T>
constexpr T power(T a, i64 b) {T res = 1;for (; b; b /= 2, a *= a) {if (b % 2) {res *= a;}}return res;
}constexpr i64 mul(i64 a, i64 b, i64 p) {i64 res = a * b - i64(1.L * a * b / p) * p;res %= p;if (res < 0) {res += p;}return res;
}
template<i64 P>
struct MLong {i64 x;constexpr MLong() : x{} {}constexpr MLong(i64 x) : x{norm(x % getMod())} {}static i64 Mod;constexpr static i64 getMod() {if (P > 0) {return P;} else {return Mod;}}constexpr static void setMod(i64 Mod_) {Mod = Mod_;}constexpr i64 norm(i64 x) const {if (x < 0) {x += getMod();}if (x >= getMod()) {x -= getMod();}return x;}constexpr i64 val() const {return x;}explicit constexpr operator i64() const {return x;}constexpr MLong operator-() const {MLong res;res.x = norm(getMod() - x);return res;}constexpr MLong inv() const {assert(x != 0);return power(*this, getMod() - 2);}constexpr MLong &operator*=(MLong rhs) & {x = mul(x, rhs.x, getMod());return *this;}constexpr MLong &operator+=(MLong rhs) & {x = norm(x + rhs.x);return *this;}constexpr MLong &operator-=(MLong rhs) & {x = norm(x - rhs.x);return *this;}constexpr MLong &operator/=(MLong rhs) & {return *this *= rhs.inv();}friend constexpr MLong operator*(MLong lhs, MLong rhs) {MLong res = lhs;res *= rhs;return res;}friend constexpr MLong operator+(MLong lhs, MLong rhs) {MLong res = lhs;res += rhs;return res;}friend constexpr MLong operator-(MLong lhs, MLong rhs) {MLong res = lhs;res -= rhs;return res;}friend constexpr MLong operator/(MLong lhs, MLong rhs) {MLong res = lhs;res /= rhs;return res;}friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {i64 v;is >> v;a = MLong(v);return is;}friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {return os << a.val();}friend constexpr bool operator==(MLong lhs, MLong rhs) {return lhs.val() == rhs.val();}friend constexpr bool operator!=(MLong lhs, MLong rhs) {return lhs.val() != rhs.val();}
};template<>
i64 MLong<0LL>::Mod = i64(1E18) + 9;template<int P>
struct MInt {int x;constexpr MInt() : x{} {}constexpr MInt(i64 x) : x{norm(x % getMod())} {}static int Mod;constexpr static int getMod() {if (P > 0) {return P;} else {return Mod;}}constexpr static void setMod(int Mod_) {Mod = Mod_;}constexpr int norm(int x) const {if (x < 0) {x += getMod();}if (x >= getMod()) {x -= getMod();}return x;}constexpr int val() const {return x;}explicit constexpr operator int() const {return x;}constexpr MInt operator-() const {MInt res;res.x = norm(getMod() - x);return res;}constexpr MInt inv() const {assert(x != 0);return power(*this, getMod() - 2);}constexpr MInt &operator*=(MInt rhs) & {x = 1LL * x * rhs.x % getMod();return *this;}constexpr MInt &operator+=(MInt rhs) & {x = norm(x + rhs.x);return *this;}constexpr MInt &operator-=(MInt rhs) & {x = norm(x - rhs.x);return *this;}constexpr MInt &operator/=(MInt rhs) & {return *this *= rhs.inv();}friend constexpr MInt operator*(MInt lhs, MInt rhs) {MInt res = lhs;res *= rhs;return res;}friend constexpr MInt operator+(MInt lhs, MInt rhs) {MInt res = lhs;res += rhs;return res;}friend constexpr MInt operator-(MInt lhs, MInt rhs) {MInt res = lhs;res -= rhs;return res;}friend constexpr MInt operator/(MInt lhs, MInt rhs) {MInt res = lhs;res /= rhs;return res;}friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {i64 v;is >> v;a = MInt(v);return is;}friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {return os << a.val();}friend constexpr bool operator==(MInt lhs, MInt rhs) {return lhs.val() == rhs.val();}friend constexpr bool operator!=(MInt lhs, MInt rhs) {return lhs.val() != rhs.val();}
};template<>
int MInt<0>::Mod = 998244353;template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();constexpr int P = 998244353;
using Z = MInt<P>;template<typename T>
class FenWick {
private:int n;std::vector<T> tr;
public:FenWick(int _n) : n(_n), tr(_n + 1) {}FenWick(const std::vector<T> &_init) : FenWick(_init.size()) {init(_init);}void init(const std::vector<T> &_init) {for (int i = 1; i <= n; ++ i) {tr[i] += _init[i - 1];int j = i + (i & -i);if (j <= n)tr[j] += tr[i];}}void add(int x, int k) {for (; x <= n; x += x & -x) tr[x] += k;}void add(int l, int r, T k) {add(l, k);if (r + 1 <= n)add(r + 1, -k);}T query(int x) const {T res = T{};for (; x; x &= x - 1) { res += tr[x];}return res;}T query(int l, int r) const {if (l > r) return T{};return query(r) - query(l - 1);}int select(int k) {int x = 0;T cur{};for (int i = 1 << std::__lg(n); i; i /= 2) {if (x + i <= n && cur + tr[x + i] < k) {x += i;cur = cur + tr[x];}}return x + 1;}void clear() {tr.assign(n + 1, T{});}
};void solve() {int n, k;std::cin >> n >> k;std::vector<int> p(n);for (int i = 0; i < n; ++ i) {std::cin >> p[i];}FenWick<Z> fen(n);Z tot = 0;for (int i = n - 1; ~i; -- i) {tot += fen.query(p[i]);fen.add(p[i], 1);}fen.clear();Z cur = 0;for (int i = k - 1; ~i; -- i) {cur += fen.query(p[i]);fen.add(p[i], 1);}Z ans = tot - cur;for (int i = 0; i + k < n; ++ i) {fen.add(p[i], -1);cur -= fen.query(p[i]);cur += fen.query(p[i + k], n);fen.add(p[i + k], 1);ans += tot - cur;}std::cout << (ans * Z(n - k + 1).inv() + Z(4).inv() * Z(k) * Z(k - 1)) << '\n';
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);#ifdef DEBUGint START = clock();freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint t = 1;// std::cin >> t;while (t --) {solve();}
#ifdef DEBUGstd::cerr << "run-time: " << clock() - START << '\n';
#endifreturn 0;
}


http://www.ppmy.cn/ops/134547.html

相关文章

【大语言模型】ACL2024论文-12 大型语言模型的能力如何受到监督式微调数据组成影响

【大语言模型】ACL2024论文-12 大型语言模型的能力如何受到监督式微调数据组成影响

【大语言模型】ACL2024论文-12 大型语言模型的能力如何受到监督式微调数据组成影响 论文&#xff1a;https://arxiv.org/pdf/2310.05492 目录 文章目录 【大语言模型】ACL2024论文-12 大型语言模型的能力如何受到监督式微调数据组成影响论文&#xff1a;https://arxiv.org/p…
阅读更多...
中心极限定理的三种形式

中心极限定理的三种形式

独立同分布的中心极限定理&#xff1a; 设 X 1 , X 2 , … , X n X_1, X_2, \ldots, X_n X1​,X2​,…,Xn​是独立同分布的随机变量序列&#xff0c;且 E ( X i ) μ E(X_i) \mu E(Xi​)μ&#xff0c; D ( X i ) σ 2 > 0 D(X_i) \sigma^2 > 0 D(Xi​)σ2>0存在…
阅读更多...
处理namespace问题:Namespace not specified for AGP 8.0.0

处理namespace问题:Namespace not specified for AGP 8.0.0

How do I fix ‘namespace not specified’ error in Android Studio? Namespace not specified for AGP 8.0.0 解决方案 <?xml version"1.0" encoding"utf-8"?> <manifest xmlns:android"http://schemas.android.com/apk/res/androi…
阅读更多...
Flink算子

Flink算子

文章目录 mapfilterflatMapkeyByaggregationsreduce物理分区算子富函数splitside outputunion(联合)connect(连接&#xff09; map Map 算子会遍历数据流的每一个元素产生一个新的元素。 public static void main(String[] args) throws Exception {StreamExecutionEnvironmen…
阅读更多...
A032-基于Spring Boot的健康医院门诊在线挂号系统

A032-基于Spring Boot的健康医院门诊在线挂号系统

&#x1f64a;作者简介&#xff1a;在校研究生&#xff0c;拥有计算机专业的研究生开发团队&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339; 赠送计算机毕业设计600…
阅读更多...
tauri开发中，使用node将png图片转成苹果的icns图标格式，解决tauri icon生成的mac图标过大问题

tauri开发中，使用node将png图片转成苹果的icns图标格式，解决tauri icon生成的mac图标过大问题

在tauri开发中&#xff0c;我们使用tauri icon生成的图标在windows上是正常的&#xff0c;但是在mac上就显示过大&#xff0c;也可以看tauri的issue&#xff1a;[v2]When using the Tauri Icon to generate icons, it is always larger than other icons in Mac tauri-apps/ta…
阅读更多...
大数据应用开发——实时数据处理（一）

大数据应用开发——实时数据处理（一）

前言 大数据应用开发——实时数据采集 大数据应用开发——实时数据处理 Flink完成Kafka中的数据消费&#xff0c;将数据分发至Kafka的dwd层中 并在HBase中进行备份 大数据应用开发——数据可视化 hadoop&#xff0c;zookeeper&#xff0c;kafka&#xff0c;flink要开启 目…
阅读更多...
SpringCloud Feign 报错 Request method ‘POST‘ not supported 的解决办法

SpringCloud Feign 报错 Request method ‘POST‘ not supported 的解决办法

Request method POST not supportedorg.springframework.web.HttpRequestMethodNotSupportedException: Request method POST not supported解决办法: 在远程调用fegin使用GET请求时 应该附加注解 RequestParam(“pgQuery”) 实体类或者单个参数同样适用 在controller接受参数…
阅读更多...
最新文章

Copyright @ 2022~2023