【11.1】【VP】Codeforces Round #729 (Div. 2)

ALL：6
AC：2
补题：2
Rank：2958

---

C. Strange Function

题意：定义 $f(i)$ 表示最小的正数满足不是 $i$ 的因子。给定 $n(1\le n\le 10^{16})$ ，求 ${\sum }_{i=1}^{n}f(i)$ 。

题解：CF1542C Strange Function

思路：假设 $x$ 是 $i$ 的最小非因子，那么一定有 $\text{lcm}(1,2,\cdots ,x-1)\mid i$ ，且 $x\nmid i$ 成立。要求只满足第一条式子的数字个数，整除一下即可。如果还需要满足第二个条件，容斥一下即可。

AC代码：https://codeforces.com/contest/1542/submission/178903704

---

D. Priority Queue

题意：

给定一个序列 $A$，$A$ 的每一个元素形如 + x 和 -，其中 $x$ 为一个整数。

对于一个每个元素都形如 + x 和 - 的序列 $S$，按如下方式计算 $f(S)$ 的值：

• 你需要依次遍历 $S$ 中的元素，并且维护一个可重集 $T$。

• 对于每个 $S$ 中的元素，若其为 + x，那么就将 $x$ 加入 $T$，否则就删除 $T$ 最小的数。特别的，若 $T$ 中没有数，那么就不进行删除操作。

• 在遍历完 $S$ 中的元素后，将可重集 $T$ 中所有数的和 $sum$ 算出来。$sum$ 即为 $f(S)$ 的值。

定义 $b$ 是 $a$ 的子序列当且仅当 $b$ 是由 $a$ 在不改变原有顺序的情况下删除若干元素得到的。现在对于 $A$ 的所有子序列 $B$，蓝想让你求出 $f(B)$ 的和模 $998244353$ 的值。

本题有 $1\le n\le 500$，并且对于每个形如 + x 元素中的 $x$，有 $1\le x<998244353$。

题解：CF1542D Priority Queue 题解

思路：这是一道细节很多的 DP 题。

考虑求每个数字 $x=a_k$ 的贡献次数，即出现在了多少个子序列中。

设 $dp(i,j)$ 表示前 $i$ 个数的所有可重子集（包括 $x$ ，表示为 { a d ∣ d ∈ [ 1 , i ] , d ≠ k } ∪ { x } \{ a_{d} |d\in[1,i],d\neq k \} \cup \{x\} {ad​∣d∈[1,i],d=k}∪{x} ）中，有 $j$ 个小于 $x$ 的数字的序列个数。

DP 方程及推导详见题解。提几个要注意的细节。

1. 对于 $o{p}_i=-$ 的情况，当 $i<k,j=0$ 时，要多转移一个，而 $i>k,j=0$ 时不能多转移（因为要考虑操作该 $op$ 时 $a_k$ 是否在集合中）。
2. 对于 $o{p}_i=+$ 的情况，如果 $a_i=a_k$ ，为了避免算重算漏，把 $i<k$ 归到一类转移，把 $i>k$ 归到另一个转移。

AC代码：https://codeforces.com/contest/1542/submission/178906123