Codeforces Round 902

__vector__ · 2023-10-08 22:28:44 · 个人记录

感觉这场比赛和 1900+ performance 的差距主要在罚时上，想完成 flag（上紫），以后的 CF 得减少大意导致的错误。

D2A

所有人得分加起来是 0。

优先让分享价格低的人分享。

显然不同数数量不会超过 3。
并且由于 i=1 时，a_i = 0，所以从后向前最后一定会变成 0，然后一直是 0。

若 k = 1，则全填 0，答案是 1。
若 k = 2，第一种情况，在第 n 个位置被 mod 成 0，然后向前一直是 0，由于最后一位要填 n 的倍数，有 \lfloor \frac{m}{n} \rfloor 种可能；第二种情况，从后向前保持一段时间不变，然后被 mod 成 0，然后一直是 0，由于最后一位要填 [0,\min(m,n-1)]，有 \min(m,n-1) 种可能。
答案是 \lfloor \frac{m}{n} \rfloor + \min(m,n-1) 种可能。
若 k = 3，则答案是总方案数减去 k=1,2 的方案数。

考虑每一个点作为黑点，算出它及它连带着加进来的数（它的倍数）的 max。

设有 cnt_i 个点使得它及它连带着加进来的数（它的倍数）的 max 是 i。

然后枚举全局 max，算出这个全局 max 在多少种情况中出现，这个情况数是：2^{\sum\limits_{i=0}^{max-1} cnt_i} \cdot (2^{cnt_{max}} - 1 )

不会。

不会。

不会。

不会。

不会。