ARC166

。。。

A - Replace C or Swap AB

模拟判断即可。

B - Make Multiples

DP，对 $a,b,c$ 状压。枚举每个数 $A_i$ 钦定为其中某几个的倍数，类似背包。

C - LU / RD Marking

考虑将网格图划分出来，借一下官方题解的图：

这样划分出的每条折线都是独立的。我们可以对每条折线单独 DP 再将方案数相乘。容易发现每条线的方案就是斐波那契数列 $f_i$。设 $n\le m$。那么答案就是：

$$(\prod_{i=1}^n f_{2i})^2 f_{2i+1}^{m-n}$$

预处理之后快速幂计算，时间复杂度 $\mathcal O(\max(n,m)+q\log(|n-m|))$。