716MX模拟赛题解

· · 个人记录

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

傻逼题。

直接出结论