在与牢大战斗两个多月后，“引爆逆天力量，追寻圆环之理的神藏奥秘”系列堂堂打赢复活赛。看来扣1真的有用！

直接做明显没前途，考虑容斥。

注意到位置 $i$ 不合法当且仅当 $a_i<a_{i-1}$ 且 $a_i|a_{i-1}$，即 $a_i$ 为 $a_{i-1}$ 的非自身因数。

考虑有一些非法位置，其他位置随便放，然后钦定非法位置的数为上一位的非自身因数。

然而注意到非法位置的方案数是不好算的，因为可能出现多个非法位置连着的情况，此时各个非法位置是不独立的。

幸运的是，由于 $a_i\le a_{i-1}/2$，每个非法位置连续段的长度不会超过 $\log m$，那我们就可以直接枚举连续段的长度进行DP。

记 $f_i$ 表示 $i$ 作为连续段结尾的容斥贡献，$s_i$ 表示前 $i$ 位的容斥贡献和，那么有

$$f_i=\sum_{j=1}^{\log m} g_j s_{i-j-1} (-1)^j$$

$$s_i=f_i+ s_{i-1}m$$

其中 $g_i$ 表示连续 $i$ 个非法位置，且前一个合法位置随便放的方案数，容易 $O(m\log m)$ 预处理。

显然DP可以矩阵优化，于是做到了 $O(\log^3 m \log n)$ 的复杂度。可能爆标了？

Bonus: 注意到DP是一个线性递推，使用 BM 算法可以做到 $O(\log m \log n \log\log m)$。