abc335_f

有一种操作, 问能形成的种类方案数

思路

状态 \(dp_i\) 表示最后一个黑方格为 \(i\) 时的方案数为 \(dp_i\)

可以推出一个收集型转移 \(dp_i = \sum \limits_{j}dp_j\) 其中 \(j \bmod a_j = i \bmod a_j\) 时间复杂度 \(O(a_j)\)

和一个扩散型转移 \(dp_i \to dp_{j + x * a_j}\) 时间复杂度 \(O(N \log_{a_j})\)

所以可以对于所以 \(a_i \le \sqrt{200000}\) 的最收集型转移, 其他最扩散型转移