Codeforces Round 979 div2 个人题解(A~E)

news/2024/10/21 7:19:58

Codeforces Round 979 div2 个人题解(A~E)

Dashboard - Codeforces Round 979 (Div. 2) - Codeforces

火车头

#define _CRT_SECURE_NO_WARNINGS 1#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <chrono>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>#define ft first
#define sd second#define yes cout << "yes\n"
#define no cout << "no\n"#define Yes cout << "Yes\n"
#define No cout << "No\n"#define YES cout << "YES\n"
#define NO cout << "NO\n"#define pb push_back
#define eb emplace_back#define all(x) x.begin(), x.end()
#define all1(x) x.begin() + 1, x.end()
#define unq_all(x) x.erase(unique(all(x)), x.end())
#define unq_all1(x) x.erase(unique(all1(x)), x.end())
#define sort_all(x) sort(all(x))
#define sort1_all(x) sort(all1(x))
#define reverse_all(x) reverse(all(x))
#define reverse1_all(x) reverse(all1(x))#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fLL#define RED cout << "\033[91m"
#define GREEN cout << "\033[92m"
#define YELLOW cout << "\033[93m"
#define BLUE cout << "\033[94m"
#define MAGENTA cout << "\033[95m"
#define CYAN cout << "\033[96m"
#define RESET cout << "\033[0m"// 红色
#define DEBUG1(x)                     \RED;                              \cout << #x << " : " << x << endl; \RESET;// 绿色
#define DEBUG2(x)                     \GREEN;                            \cout << #x << " : " << x << endl; \RESET;// 蓝色
#define DEBUG3(x)                     \BLUE;                             \cout << #x << " : " << x << endl; \RESET;// 品红
#define DEBUG4(x)                     \MAGENTA;                          \cout << #x << " : " << x << endl; \RESET;// 青色
#define DEBUG5(x)                     \CYAN;                             \cout << #x << " : " << x << endl; \RESET;// 黄色
#define DEBUG6(x)                     \YELLOW;                           \cout << #x << " : " << x << endl; \RESET;using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// typedef __int128_t i128;typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef pair<ll, int> pli;
typedef pair<string, string> pss;
typedef pair<string, int> psi;
typedef pair<string, ll> psl;typedef tuple<int, int, int> ti3;
typedef tuple<ll, ll, ll> tl3;
typedef tuple<ld, ld, ld> tld3;typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pli> vpli;
typedef vector<pss> vpss;
typedef vector<ti3> vti3;
typedef vector<tl3> vtl3;
typedef vector<tld3> vtld3;typedef vector<vi> vvi;
typedef vector<vl> vvl;typedef queue<int> qi;
typedef queue<ll> ql;
typedef queue<pii> qpii;
typedef queue<pll> qpll;
typedef queue<psi> qpsi;
typedef queue<psl> qpsl;typedef priority_queue<int> pqi;
typedef priority_queue<ll> pql;
typedef priority_queue<string> pqs;
typedef priority_queue<pii> pqpii;
typedef priority_queue<psi> pqpsi;
typedef priority_queue<pll> pqpll;
typedef priority_queue<psi> pqpsl;typedef map<int, int> mii;
typedef map<int, bool> mib;
typedef map<ll, ll> mll;
typedef map<ll, bool> mlb;
typedef map<char, int> mci;
typedef map<char, ll> mcl;
typedef map<char, bool> mcb;
typedef map<string, int> msi;
typedef map<string, ll> msl;
typedef map<int, bool> mib;typedef unordered_map<int, int> umii;
typedef unordered_map<ll, ll> uml;
typedef unordered_map<char, int> umci;
typedef unordered_map<char, ll> umcl;
typedef unordered_map<string, int> umsi;
typedef unordered_map<string, ll> umsl;std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());template <typename T>
inline T read()
{T x = 0;int y = 1;char ch = getchar();while (ch > '9' || ch < '0'){if (ch == '-')y = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = (x << 3) + (x << 1) + (ch ^ 48);ch = getchar();}return x * y;
}template <typename T>
inline void write(T x)
{if (x < 0){putchar('-');x = -x;}if (x >= 10){write(x / 10);}putchar(x % 10 + '0');
}/*#####################################BEGIN#####################################*/
void solve()
{
}int main()
{ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);// freopen("test.in", "r", stdin);// freopen("test.out", "w", stdout);int _ = 1;std::cin >> _;while (_--){solve();}return 0;
}/*######################################END######################################*/
// 链接：

A. A Gift From Orangutan

A. 来自猩猩的礼物
时间限制：每个测试1秒
内存限制：256兆字节

在丛林探险时，你遇到了一只戴着领结的稀有猩猩！你和猩猩握手，并给他一些食物和水。作为回报……

猩猩送给你一个长度为 $n$ 的数组 $a$。使用 $a$，你将构建两个数组 $b$ 和 $c$，它们都包含 $n$ 个元素，方式如下：

每个 $1 \leq i \leq n$ 对应 $b_i = \min(a_1, a_2, \ldots, a_i)$。
每个 $1 \leq i \leq n$ 对应 $c_i = \max(a_1, a_2, \ldots, a_i)$。
将 $a$ 的得分定义为 $\sum_{i=1}^{n}(c_i - b_i)$（即 $c_i - b_i$ 与所有 $1 \leq i \leq n$ 之和）。在计算得分之前，您可以随意打乱 $a$ 的元素。

找出以最佳方式打乱 $a$ 的元素时可以获得的最大得分。

输入
第一行包含 $t$ ($1 \leq t \leq 100$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($1 \leq n \leq 1000$) — $a$ 中的元素数量。

下一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 1000$) — 数组 $a$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $1000$。

输出
对于每个测试用例，输出你能得到的最高分数。

示例
输入

输出

0  
4  
4

备注
在第一个测试用例中，没有其他方法可以重新排列 $a$。因此，$b = [69]$ 和 $c = [69]$。唯一可能的得分是 $69 - 69 = 0$。

在第二个测试用例中，你可以将 $a$ 重新排列为 $[7, 5, 6]$。这里，$b = [7, 5, 5]$ 和 $c = [7, 7, 7]$。在这种情况下的得分是 $(7 - 7) + (7 - 5) + (7 - 5) = 4$。可以证明这是最大可能得分。

解题思路

我们可以获得的最大极差是最大值$mx$减最小值$mn$，所以只需要找出最大和最小值算出极差然后乘以$n-1$即可

代码实现

void solve()
{int n;cin >> n;int mx = 0;int mn = inf;for (int i = 0; i < n; i++){int x;cin >> x;mx = max(mx, x);mn = min(mn, x);}cout << 1ll * (n - 1) * (mx - mn) << endl;
}

B. Minimise Oneness

时间限制：每个测试1.5秒
内存限制：256兆字节

对于任意二进制字符串 $t$，令 $f(t)$ 为 $t$ 中仅包含 $0$ 的非空子序列的数量，令 $g(t)$ 为 $t$ 中至少包含一个 $1$ 的非空子序列的数量。

我们将二进制字符串 $t$ 的一元性定义为 $|f(t)−g(t)|$，其中对于任意整数 $z$，$|z|$ 表示 $z$ 的绝对值。

给定一个正整数 $n$。查找长度为 $n$ 的二进制字符串 $s$，使得其一性尽可能小。如果有多个字符串，则可以打印其中任何一个。

输入
第一行包含一个整数 $t$ ($1 \leq t \leq 10^4$) — 测试用例的数量。

每个测试用例的唯一一行包含一个整数 $n$ ($1 \leq n \leq 2 \cdot 10^5$) — $s$ 的长度。

保证所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

输出
对于每个测试用例，在新行上输出 $s$。如果存在多个答案，则输出任意一个。

示例
输入

输出

0  
01  
010

备注
在第一个测试用例中，输出示例中 $f(t)=1$，因为有一个仅包含 $0$ 的子序列（$0$），而 $g(t)=0$，因为没有包含至少一个 $1$ 的子序列。一元性为 $|1−0|=1$。输出 $1$ 也是正确的，因为它的一元性为 $|0−1|=1$。

在第二个测试用例中，输出示例中 $f(t)=1$，因为有一个仅包含 $0$ 的非空子序列，而 $g(t)=2$，因为有两个至少包含一个 $1$ 的非空子序列（$01$ 和 $1$）。因此一元性为 $|1−2|=1$。可以证明这是所有可能长度为 $2$ 的二进制字符串中一元性的最小值。

解题思路

记字符串$t$中$0$的数量为$n0$，$1$的数量为$n1$，易得$f(t)=2^{n0}-1$，$g(t)=2^{n0}\times(2^{n1}-1)$。

\[|f(t) - g(t)| = |(2^{n0} - 1) - (2^{n0} \times (2^{n1} - 1))| \]

展开 $ g(t) $：

\[g(t) = 2^{n0} \times (2^{n1} - 1) = 2^{n0 + n1} - 2^{n0} \]

代入 $ g(t) $ 的表达式：

\[|f(t) - g(t)| = |(2^{n0} - 1) - (2^{n0 + n1} - 2^{n0})| \]

\[= |2^{n0} - 1 - 2^{n0 + n1} + 2^{n0}| \]

\[= |2 \cdot 2^{n0} - 1 - 2^{n0 + n1}| \]

\[= |2^{n0 + 1} - 2^{n0 + n1}-1| \]

这里我们可以考虑两种情况：

如果 $ n1 = 0 $，则 $ g(t) = 0 $，此时 $ |f(t) - g(t)| = |2^{n0} - 1| $。
如果 $ n1 > 0 $，则 $ 2^{n0 + n1} $ 会大于 $ 2^{n0 + 1} $，所以：

\[|f(t) - g(t)| = 2^{n0 + n1} - 2^{n0 + 1} - 1 \]

最终结果为：

\[|f(t) - g(t)| = |2^{n0 + 1} - 2^{n0 + n1} - 1| \]

当$n1=1$时值最小

代码实现

void solve()
{int n;cin >> n;string s(n - 1, '0');s += "1";cout << s << endl;
}

C. A TRUE Battle

时间限制：每个测试2秒
内存限制：256兆字节

Alice 和 Bob 正在玩游戏。有一个包含 $n$ 个布尔值的列表，每个布尔值要么为真，要么为假，以长度为 $n$ 的二进制字符串给出（其中 $1$ 表示真，而 $0$ 表示假）。最初，布尔值之间没有运算符。

Alice 和 Bob 将轮流在布尔值之间放置 and 或 or，Alice 先走。因此，游戏将由 $n−1$ 个回合组成，因为有 $n$ 个布尔值。Alice 的目标是让最后一个语句的计算结果为真，而 Bob 的目标是让它的计算结果为假。给定布尔值列表，确定如果两个玩家都发挥最佳水平，Alice 是否会获胜。

要计算最终表达式的值，请重复执行以下步骤，直到语句由单个真或假组成：

如果语句包含 and 运算符，请选择任意一个并将其周围的子表达式替换为其计算值。
否则，语句包含 or 运算符。请选择任意一个并将其周围的子表达式替换为其计算值。

例如，表达式 true or false and false 的计算结果为 true or (false and false) = true or false = true。可以证明任何复合语句的结果都是唯一的。

输入
第一行包含 $t$ ($1 \leq t \leq 10^4$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($2 \leq n \leq 2 \cdot 10^5$) — 字符串的长度。

第二行包含一个长度为 $n$ 的二进制字符串，由字符 $0$ 和 $1$ — 布尔值列表组成。

保证所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

输出
对于每个测试用例，如果 Alice 获胜，则输出“YES”（不带引号），否则输出“NO”（不带引号）。

您可以在任何情况下输出“YES”和“NO”（例如，字符串“yES”、“yes”和“Yes”将被识别为肯定响应）。

示例
输入

5  
2  
11  
3  
010  
12  
101111111100  
10  
0111111011  
8  
01000010

输出

YES  
NO  
YES  
YES  
NO

备注
在第一个测试用例中，Alice 可以在两个布尔值之间放置 and。游戏结束，因为没有其他地方可以放置运算符，Alice 赢得比赛，因为 true and true 是 true。

在第二个测试用例中，Alice 可以在中间的 true 和左边的 false 之间放置 or。Bob 可以在中间的 true 和右边的 false 之间放置 and。语句 false or true and false 是 false。

注意，这些示例可能不是 Alice 或 Bob 的最佳策略。

解题思路

对于在最左边的1来说，如果我们在其右边插入一个or，那么无论右边最后算出来是什么结果，都无法改变它，对于最右边的1同理。

所以如果字符串首或尾有1则Yes。

对于子串"11"来说，我们一定可以构成"... or 1 ... 1 or ..."或"... 1 or 1 or ...."的形式使得1无法被消除，所以如果字符串存在“11”，则Yes

其它情况则No

代码实现

void solve()
{int n;cin >> n;string s;cin >> s;if (s.front() == '1' || s.back() == '1' || s.find("11") != string::npos)YES;elseNO;
}

D. QED's Favorite Permutation

时间限制：每个测试2秒
内存限制：256兆字节

QED 被赋予一个长度为 $n$ 的排列 $p$。他还有一个长度为 $n$ 的字符串 $s$，其中仅包含字符 $L$ 和 $R$。QED 只喜欢按非递减顺序排序的排列。要对 $p$ 进行排序，他可以选择以下任何操作并执行任意次数：

选择一个索引 $i$，使得 $s_i = L$。然后，交换 $p_i$ 和 $p_{i-1}$。保证 $s_1 \neq L$。
选择一个索引 $i$，使得 $s_i = R$。然后，交换 $p_i$ 和 $p_{i+1}$。保证 $s_n \neq R$。

他还被给予 $q$ 个查询。在每个查询中，他选择一个索引 $i$，并将 $s_i$ 从 $L$ 更改为 $R$（或从 $R$ 更改为 $L$）。请注意，这些更改是持久的。

每次查询后，他都会询问您是否可以通过执行上述操作任意多次以非递减顺序对 $p$ 进行排序。请注意，在回答每个查询之前，排列 $p$ 会重置为其原始形式。

输入
第一行包含 $t$ ($1 \leq t \leq 10^4$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $q$ ($3 \leq n \leq 2 \cdot 10^5$, $1 \leq q \leq 2 \cdot 10^5$) — 排列的长度和查询的数量。

下一行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$ ($1 \leq p_i \leq n$, $p$ 是排列)。

下一行包含 $n$ 个字符 $s_1 s_2 \ldots s_n$。保证 $s_i$ 为 $L$ 或 $R$、$s_1 = R$ 和 $s_n = L$。

以下 $q$ 行包含一个整数 $i$ ($2 \leq i \leq n-1$)，表示 $s_i$ 从 $L$ 更改为 $R$（或从 $R$ 更改为 $L$）。

保证所有测试用例的 $n$ 和 $q$ 之和不超过 $2 \cdot 10^5$。

输出
对于每个查询，如果可能则输出“YES”（不带引号），否则输出“NO”（不带引号）。

您可以在任何情况下输出“YES”和“NO”（例如，字符串“yES”、“yes”和“Yes”将被识别为肯定响应）。

示例
输入

3  
5 3  
1 4 2 5 3  
RLRLL  
2  
4  
3  
8 5  
1 5 2 4 8 3 6 7  
RRLLRRRL  
4  
3  
5  
3  
4  
6 2  
1 2 3 4 5 6  
RLRLRL  
4  
5

输出

YES  
YES  
NO  
NO  
YES  
NO  
NO  
NO  
YES  
YES

备注
在第一个测试用例中，第一个查询后的 $s = RRRLL$。QED 可以使用以下操作对 $p$ 进行排序：

最初，$p = [1, 4, 2, 5, 3]$。
选择 $i=2$ 并将 $p_2$ 与 $p_3$ 交换。现在，$p = [1, 2, 4, 5, 3]$。
选择 $i=5$ 并将 $p_5$ 与 $p_4$ 交换。现在，$p = [1, 2, 4, 3, 5]$。
选择 $i=4$ 并将 $p_4$ 与 $p_3$ 交换。现在，$p = [1, 2, 3, 4, 5]$，这是非递减顺序。

可以证明，第一个测试用例三次更新后，不可能对数组进行排序。

解题思路

观察题目可得两个性质

设$R=0,L=1$，对于任何非递减序的子段，我们可以任意重排里面的元素
对于任意子数组$p_{l},p_{l+1},p_{l+2},\dots,p_{r}$满足$l=min(p_i),l\le i\le r $且$r=max(p_i),l\le i\le r $，我们需要重排$p_i,l\le i\le r$

所以，我们可以根据性质2，对排列$p$进行分段，对每一段计算其逆序对数量。算出每段逆序对数总和。如果总和为零，说明可以重排。

每次更改计算一下对该段逆序对的影响，然后加到总和中。

计算逆序对可以使用树状树状或线段树。

时间复杂度为$O(n\log(n))$

其实维护LR数量就行了，不需要维护逆序对数量。赛时树状数组板子出问题了，写半天没找到bug在哪，一直wa2，还以为逆序对算错了，赛后才发现是板子有问题，人麻了

代码实现

struct seg
{int l, r;seg() : l(0), r(0) {}seg(int _l, int _r) : l(_l), r(_r) {}bool operator<(const seg &rhs) const{return l < rhs.l;}
};template <typename T>
struct Fenwick
{int n;vector<T> a;Fenwick(int n_ = 0){init(n_);}void init(int n_){n = n_;a.assign(n + 1, T{});}void add(int x, const T &v){for (int i = x; i <= n; i += i & -i){a[i] = a[i] + v;}}T sum(int x){T ans{};for (int i = x; i > 0; i -= i & -i){ans = ans + a[i];}return ans;}T rangeSum(int l, int r){return sum(r) - sum(l - 1);}
};void solve()
{int n, q;cin >> n >> q;vi a(n + 1);for (int i = 1; i <= n; i++){cin >> a[i];}int mx = 0;       // 最大值int l = 1, r = 1; // 左右指针set<seg> st;      // 存储可排序的区间for (int i = 1; i <= n; i++, r++){mx = max(mx, a[i]); // 更新最大值if (mx == r){                      // 如果当前最大值等于右指针st.insert({l, r}); // 将区间[l, r]插入集合l = i + 1;         // 更新左指针}}string s;cin >> s;s = " " + s;Fenwick<int> cntR(n + 1); // 维护R的数量Fenwick<int> cntL(n + 1); // 维护L的数量for (int i = 1; i <= n; i++){if (s[i] == 'R')cntR.add(i, 1);elsecntL.add(i, 1);}long long sum = 0; // 统计逆序对的总和for (auto it : st){                           // 遍历可排序的区间int l = it.l, r = it.r; // 取出区间的左右端点for (int i = l; i <= r; i++){if (s[i] == 'R')                // 如果当前是Rsum += cntL.rangeSum(l, i); // 统计逆序对}}while (q--){                                     // 处理每个查询int p;                            // 查询的索引cin >> p;                         // 输入查询索引auto it = st.upper_bound({p, p}); // 找到p的上界it = prev(it);                    // 获取p的前一个区间int l = it->l, r = it->r;         // 获取区间的左右端点if (s[p] == 'R'){                               // 如果当前是Rsum -= cntL.rangeSum(l, p); // 减去当前逆序对cntL.add(p, 1);             // 更新LcntR.add(p, -1);            // 更新Rs[p] = 'L';                 // 改变方向sum += cntR.rangeSum(p, r); // 加上新的逆序对}else{                               // 如果当前是Lsum -= cntR.rangeSum(p, r); // 减去当前逆序对cntL.add(p, -1);            // 更新LcntR.add(p, 1);             // 更新Rs[p] = 'R';                 // 改变方向sum += cntL.rangeSum(l, p); // 加上新的逆序对}if (sum == 0)        // 如果逆序对总数为0cout << "YES\n"; // 可以排序elsecout << "NO\n"; // 不能排序}
}

E. MEXimize the Score

时间限制：每个测试2秒
内存限制：256兆字节

假设我们将数组 $b$ 的元素划分为任意数量 $k$ 的非空多集 $S_1, S_2, \ldots, S_k$，其中 $k$ 为任意正整数。将 $b$ 的得分定义为 $b$ 的所有可能分区中任意整数 $k$ 的最大值 $MEX(S_1) + MEX(S_2) + \ldots + MEX(S_k)$。

Envy 被赋予一个大小为 $n$ 的数组 $a$。因为他知道计算 $a$ 的分数对你来说太容易了，所以他要求你计算 $a$ 的所有 $2^{n}-1$ 个非空子序列的分数之和。由于这个答案可能很大，请输出它对 $998244353$ 取模的结果。

整数集合 $c_1, c_2, \ldots, c_k$ 中的 $MEX$ 定义为集合 $c$ 中未出现的最小非负整数 $x$。例如，$MEX([0,1,2,2])=3$ 和 $MEX([1,2,2])=0$。

如果可以通过删除几个（可能是零个或全部）元素从 $y$ 中获得 $x$，则序列 $x$ 是序列 $y$ 的子序列。

输入
第一行包含一个整数 $t$ ($1 \leq t \leq 10^4$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($1 \leq n \leq 2 \cdot 10^5$) — $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($0 \leq a_i < n$) — 数组 $a$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出
对于每个测试用例，输出答案，模数为 $998244353$。

示例
输入

输出

备注
在第一个测试用例中，我们必须考虑七个子序列：

$[0]$：得分为 $1$。
$[0]$：得分为 $1$。
$[1]$：得分为 $0$。
$[0,0]$：得分为 $2$。
$[0,1]$：得分为 $2$。
$[0,1]$：得分为 $2$。
$[0,0,1]$：得分为 $3$。

第一个测试用例的答案是 $1 + 1 + 2 + 2 + 2 + 3 = 11$。

在最后一个测试用例中，所有子序列的得分都是 $0$。

解题思路

观察发现分数 $ b $ 等价于 $cnt_0 + \min(cnt_0, cnt_1) + \ldots + \min(cnt_0, \ldots, cnt_{n-1}) $，其中 $ cnt_i $ 表示 $i$在$ b $的出现次数。

我们可以贪心地构造这 $ k $ 个分区，每次选择最小的 $ j $ 使得 $ cnt_j = 0 $ 且 $ \min(cnt_0, \ldots, cnt_{-1}) > 0 $，得到分区 $ [0, 1, \ldots, j-1] $。

这是最优的，因为我们添加的每个元素都会使 MEX 增加 $ 1 $，从而使分数增加 $ 1 $。如果我们添加 $ j $，MEX 不会增加。此外，当我们添加一个元素时，分数的增加不会超过 $ 1 $。添加少于 $ j $ 的元素无法增加未来数组的 MEX。

所以我们可以枚举分区数$k$，对$k$分区下的最大$\text{mex}$进行贡献计算

对于$i\lt \text{mex}$的方案选择总数的贡献为 $f_i= \sum_{k=j}^{cnt_i} C _{cnt_i}^{k} \cdot f_{i-1}$

对于$i\gt mex$的方案选择总数的贡献为$2^{\sum_{j=mex}^{n}{cnt_j}}$，我们可以使用后缀数组快速求出

最后把两者相乘加入答案

代码实现

void solve()
{int n;cin >> n;vector<int> cnt(n);// 统计数组 a 中每个值的出现频次for (int i = 0; i < n; i++){int x;cin >> x;cnt[x]++;}vector<int> suf(n); // suf 数组用于存储从第 i 个位置开始，到数组末尾的后缀积suf[n - 1] = 1;     // 最后一个元素的后缀积设为 1，因为 suf 数组是为每个位置计算贡献做准备的// 逆序计算每个位置的后缀积， suf[i] 表示从位置 i 到末尾，每个 mex 值增加的贡献倍数for (int i = n - 2; i >= 0; i--){suf[i] = suf[i + 1] * qmi(2, cnt[i + 1]) % mod;}ll ans = 0;            // 最终答案vector<ll> f(n);       // f 数组用于记录每个元素对当前 MEX 的贡献vector<int> num = cnt; // num 用来逐步减少每个元素的频次，以此来模拟分区过程int p = 0;             // 指针 p 用来追踪当前 MEX 的上限// 枚举分区数 k，k 从 n 开始逐步减少到 1for (int k = n; k >= 1; k--){// 找到最大的满足 cnt[p] >= k 的 p 值，p 用于控制当前可以包含的 mex 最大值while (p < n && cnt[p] >= k){p++; // p 逐步向右移动，直到找到第一个 cnt[p] < k 的元素}ll res = 1; // 当前分区中子序列贡献的乘积，初始为 1// 遍历 [0, p-1] 区间的元素，计算它们的贡献for (int i = 0; i < p; i++){// num[i] 表示元素 i 还能使用的剩余次数，如果 num[i] >= k，说明该元素还能进入分区while (num[i] >= k){// 使用组合数计算 cnt[i] 中取出 num[i] 次的方法数，并累加到 f[i] 中f[i] = (f[i] + C(cnt[i], num[i])) % mod;num[i]--; // 每次使用完 num[i]，它的频次就减少 1}// 将每个元素 i 的贡献乘以 res，更新 resres = res * f[i] % mod;// 将当前分区的贡献加到总答案中，同时乘以 suf[i] 表示后缀的贡献ans = (ans + res * suf[i] % mod) % mod;}}cout << ans << endl;
}

这场掉100多分，爆炸

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.ryyt.cn/news/74026.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈，一经查实，立即删除！