【题解】AtCoder-ARC167-526互联

AtCoder-ARC167A Toasts for Breakfast Party

一定不会有空盘，问题转化成 \(2m\) 个数，其中 \(2m-n\) 个是 \(0\)，这样一定是最大值和最小值一起，次大值和次小值一起，以此类推。

\(A^B=\prod_i p_i^{Bc_i}\)，那么答案就是求：

\[\min_{i}\left\{\dfrac{1}{c_i}\times \dfrac{Bc_i(Bc_i+1)}{2}\times \prod_{j\neq i}(Bc_j+1)\right\} \]

发现直接变成求：

\[\left\lfloor\dfrac{B\prod_i (Bc_i+1)}{2}\right\rfloor\bmod 998244353 \]

直接维护商模 \(998244353\) 的值和余数即可。

不会。

要求 \(i\to p_i\) 连边得到一个环，每次交换等价于合并所在两个环。

考虑从小到大枚举每个值 \(k\)，如果与 \(1\) 不在同一环则交换并合并，交换一定是选第一个大于 \(k\) 的位置或者 \(k-1\)。

容易发现每个环的位置集合和数值集合相同，所以枚举到 \(k\) 时 \([1,k-1]\) 位置上的数都和 \(1\) 在同一环中，同时由于 \(k\) 的单调性，交换的位置也是单调的，维护一个指针即可。

不会。

不会。