Description：

将每个数指定 $m$ 种颜色之一，求合法的方案数。对于三个数 $k,2k,3k$ ，如果它们都同色，那么不合法。

$1\leqslant n\leqslant 200000$

Solution：

将每个数表示成 $2^x3^yz$ 的形式，那么对于 $z$ 不同的数互不干扰，可以分别统计最后乘起来，那么我们把每个数放到矩阵上，就是要求 $(x,y),(x+1,y),(x,y+1)$ 如果他们都存在的话不能同色，这时候我们就有一个轮廓线 $DP$ 的思路，记录轮廓线上的颜色转移，但是复杂度过不去。

考虑容斥，强制 $k$ 个三元组同色，那么如果有 $tot$ 个连通块，对答案的贡献是 $(-1)^km^{tot}$ ，还是利用轮廓线 $DP$ ，但是我们像插头 $DP$ 一样记录轮廓线上的连通性，在封闭一个连通块的时候给答案乘 $m$ ，出现三元组同色的时候给答案乘 $-1$ ，最后累加到答案里即可。

Code：

没有代码