本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-16 19:45:14

A

不会，不写了。

B

是个好题。

20分暴力，40分容斥+子集枚举（挺简单的），100分容斥+动归。

我们发现，

设 $f_{i,j}$ 为表示 $[1, i]$ 不被 $a$ 数组中的元素整除的数有多少个。

初始化 $f_{i,0}=i$ 。

我们可以很简单的推出状态转移方程

$$f_{i,j}=f_{i,j-1}-f_{i÷a_j , j-1} $$

但是我们发现，数据范围不可取，$n<=10^{13}$，数组炸了。

但是我们可以用记忆化搜索，这正是这道题的精妙之处。

当 $n<=10000$ 时，我们可以用动规，否则，我们可以用记忆化搜索做，时间复杂度刚好不炸。

（听说将数组sort之后速度会提升许多，不知道为什么）

C

线段树。

有三种方式合并

1111111 ---- 111111111

000000------- 000000

111111 ---- 000000

求最长01串。

思路会，只可惜不会打，暴力20分。

D

傻逼题。

直接出结论