顺德网站制作案例市场,网站建设相关行业有哪些,仿站网站开发,好的办公室设计目录
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解 一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
G - Another Shuffle Window 二、解题报告
1、思路分析
不难用树状数组计…目录
一、题目
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;templateclass 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;
}
templatei64 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 MLong0LL::Mod i64(1E18) 9;templateint 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 MInt0::Mod 998244353;templateint V, int P
constexpr MIntP CInv MIntP(V).inv();constexpr int P 998244353;
using Z MIntP;templatetypename T
class FenWick {
private:int n;std::vectorT tr;
public:FenWick(int _n) : n(_n), tr(_n 1) {}FenWick(const std::vectorT _init) : FenWick(_init.size()) {init(_init);}void init(const std::vectorT _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::vectorint p(n);for (int i 0; i n; i) {std::cin p[i];}FenWickZ 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;
}
