CF585E Present for Vitalik the Philatelist

题意：给出序列 。

求满足如下条件的一个元素 和一个序列 的方案数。

• 是 的非空子序列

• ，。

两种方案不同，当且仅当 不同或者选出 的方式不同。

答案对 取模。，，时限 。

---

简单练习题。设

• 。

• 为 中 的出现次数。

• 为 的方案数。

• 为 中与 互质的数的个数。

显然有 ，，后者不必考虑。

计算

其中 ，即 的倍数求和。 是 的约数求和。

计算

设 为 为 的倍数的方案数。

考虑 可选的元素个数，显然是 ，要求选非空子集，那么 。

作倍数差分即可从 求出 。

“倍数求和”，“倍数差分”，“约数求和” 都能做到 。