Codeforces Round 1028 (Div. 2) B. Gellyfish and Baby‘s Breath

Codeforces Round 1028 (Div. 2) B. Gellyfish and Baby’s Breath

题目

Flower gives Gellyfish two permutations${}^{\text{∗}}$ of $[0,1,\dots ,n-1]$: $p_0,p_1,\dots ,p_{n-1}$ and $q_0,q_1,\dots ,q_{n-1}$.

Now Gellyfish wants to calculate an array $r_0,r_1,\dots ,r_{n-1}$ through the following method:

• For all $i$ ($0\le i\le n-1$), $r_i=\underset{j=0}{\overset{i}{\max }}\left(2^{p_j}+2^{q_{i-j}}\right)$

But since Gellyfish is very lazy, you have to help her figure out the elements of $r$.

Since the elements of $r$ are very large, you are only required to output the elements of $r$ modulo $998244353$.

${}^{\text{∗}}$An array $b$ is a permutation of an array $a$ if $b$ consists of the elements of $a$ in arbitrary order. For example, $[4,2,3,4]$ is a permutation of $[3,2,4,4]$ while $[1,2,2]$ is not a permutation of $[1,2,3]$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1\le n\le 10^5$).

The second line of each test case contains $n$ integers $p_0,p_1,\dots ,p_{n-1}$ (KaTeX parse error: Expected 'EOF', got '&' at position 12: 0 \leq p_i &̲lt; n).

The third line of each test case contains $n$ integers $q_0,q_1,\dots ,q_{n-1}$ (KaTeX parse error: Expected 'EOF', got '&' at position 12: 0 \leq q_i &̲lt; n).

It is guaranteed that both $p$ and $q$ are permutations of $[0,1,\dots ,n-1]$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output $n$ integers $r_0,r_1,\dots ,r_{n-1}$ in a single line, modulo $998244353$.

题目解析及思路

题目要求对于两个[0,...,n]的排列p，q ，求出r的所有元素

样例输入

3
0 2 1
1 2 0

样例输出

3 6 8 

• $r_0=2^{p_0}+2^{q_0}=1+2=3$
• $r_1=\max (2^{p_0}+2^{q_1},2^{p_1}+2^{q_0})=\max (1+4,4+2)=6$
• $r_2=\max (2^{p_0}+2^{q_2},2^{p_1}+2^{q_1},2^{p_2}+2^{q_0})=(1+1,4+4,2+2)=8$

代码

/*
首先是贪心的考虑：r的最终取值一定会取最大的p或最大的q构成的组合
维护两个对组pp和qq,从前往后枚举不同区间时 first存此前最大的p(q),second存对应的q(p)，方便在后续找最大时调用
*/
#include <bits/stdc++.h>
using namespace std;using ll = long long;#define MOD 998244353//快速幂求2的n次方
ll mod_pow(ll base, ll exp, ll mod) {ll result = 1;base %= mod;while (exp > 0) {if (exp & 1) result = result * base % MOD;base = base * base % MOD;exp >>= 1;}return result;
}void solve() {int n;cin >> n;vector<int> p(n), q(n);for (auto &i : p) cin >> i;for (auto &i : q) cin >> i;vector<pair<int, int>> pp(n), qq(n);//维护最大p和最大p的下标int max_p = -1, ind_p = -1;for (int i = 0; i < n; i++) {if (max_p < p[i] ) {max_p = p[i];ind_p = i;}pp[i].first = max_p;//i-ind为对应的q的下标，second存对应qpp[i].second = (i - ind_p >= 0) ? q[i - ind_p] : 0;}//同理求qqint max_q = -1, ind_q = -1;for (int i = 0; i < n; i++) {if (max_q < q[i] ) {max_q = q[i];ind_q = i;}qq[i].first = max_q;//存对应pqq[i].second = (i - ind_q >= 0) ? p[i - ind_q] : 0;}vector<ll> r(n);for (int i = 0; i < n; i++) {//a1,a2为最大p和对应qll a1 = mod_pow(2, pp[i].first, MOD);ll a2 = mod_pow(2, pp[i].second, MOD);//b1,b2为最大q和对应pll b1 = mod_pow(2, qq[i].first, MOD);ll b2 = mod_pow(2, qq[i].second, MOD);//如果第一个组合中最大值比第二个组合中最大值还*大*//肯定取第一个组合if (max(pp[i].first,pp[i].second) > max(qq[i].first,qq[i].second)) {r[i] = (a1 + a2) % MOD;}//如果第一个组合中最大值比第二个组合中最大值还*小*//肯定取第二个组合else if(max(pp[i].first,pp[i].second) < max(qq[i].first,qq[i].second)){r[i] = (b1 + b2) % MOD;}//如果最大值相同，比另一个值/比二者之和 两种方法都可以else if(pp[i].first+pp[i].second > qq[i].first+qq[i].second){r[i] = (a1 + a2) % MOD;}else {r[i] = (b1 + b2) % MOD;}}for (int i = 0; i < n; i++) {cout << r[i] << " ";}cout << "\n";
}int main() {ios::sync_with_stdio(false);cin.tie(0);ll t;cin >> t;while (t--) {solve();}return 0;
}