CF1946F Nobody is needed

· · 个人记录

考虑到如果是整个区间怎么做。设 f_i 表示以 i 为结尾的合法子序列数量。那么

f_i = 1 + \sum\limits_{j\lt i, a_j\mid a_i} f_j

考虑可以扫描线。固定左端点，从后往前，考虑 i 作为左端点对于后面的贡献。那么，所有是 a_i 的的倍数的 \arg a_i\mid a_j，都可以使得 f_j 加上 1。同时，可以间接转移，也就是使得 a_i\mid a_j\mid a_k 的 f_k 上头加上 f_j。

我们这么样就做完了。