CF738 div2 VP 总结

主要是 $\tt Alkaid$ 这个老哥要打。然后早上我在写题，写完了发现他还在搞 $C$。那就顺便打一下。

感觉上我的水平 $E$ 是做不出来的。

因为我一直在想质因数分解 $\dots$

睿智题目，题目上说操作次数是无限的，所以最终答案每个数都能被 $&$ 一次。因为 $&$ 后的值不会变大，最终答案就是每个数 $&$。

因为我比较懒直接一个 $dp$ 就搞完了。

设 $f(i, 0/1)$ 表示考虑到当前位，当前填 $R/B$ 的最小花费。

最终答案肯定一一条链再到 $n + 1$ 再回来继续链。注意特判可以从 $n + 1$ 当做起点的情况。

猜测一下最终图肯定有一个是树。

如果说不是树，那么有两个联通块 $A, B$ 在一个图上不联通，在另一个图上联通。设其为 $C$。如果 $C, D$ 不联通，在另一个图上肯定 $C, D$ 联通。通过归纳法可以得到肯定有个图是树。

既然最终是树那么暴力枚举即可。

都说了是树，那么我们考虑对于集合的连边情况，如果说一个联通块无法连边，那么肯定是其所有节点都被限制了。

我们不妨考虑让所有联通块去连接一个超级原点。如果两个位置都能连接，那么可以直接加边。如果都不能连接就是本身在联通块上。如果一个位置能连一个位置不能，那么这两个位置就可以相互连边。

$E$

这里可能会想到分解质因数，但是为什么是错的，详情见下文题解。

如果不考虑 $\gcd$ 的限制的话，考虑使用背包。

$f(i, j)$ 表示考虑了前 $i$ 个数，和是 $j$ 的方案数。
$$
f(i, j) = \sum_{i = l_i} ^ {r_i} f(i - 1, j - i)
$$
复杂度是 $O(nm)$ 的。

然后考虑公约数的限制，直接考虑 $\gcd = 1$ 的情况是不好处理的。我们需要知道质因子，但是对于一个区间的情况显然是不可取的。

我们考虑使用容斥。设 $ans_i$ 为序列公约数恰好是 $i$ 的方案数。

那么我们对于 $f$ 进行转移的时候，需要注意保证公约数至少是 $\gcd$ 。然后进行容斥即可。

如果说公约数是 $\gcd$ 的话，我们考虑让所有数字都 $\div \gcd$ 也是成立的。之后直接进行上文的 $dp$ 即可。