主要思路
蛮好想。考虑暴力,求完两者之间的\(\gcd\)之后枚举最大的因数即为答案。那么如何加速?我们发现\(gcd\)的最大因素也一定是\(a_1\)的因数之一,所以我们直接预处理\(a_i\)的因数,然后回答询问时直接\(\log n\)枚举即可。
蛮好想。考虑暴力,求完两者之间的\(\gcd\)之后枚举最大的因数即为答案。那么如何加速?我们发现\(gcd\)的最大因素也一定是\(a_1\)的因数之一,所以我们直接预处理\(a_i\)的因数,然后回答询问时直接\(\log n\)枚举即可。
树的结构让某些数据难以直接快速合并,所以就有了树上启发式合并,一种把合并时间为\(O(n)\)优化成\(O(\log n)\)的神奇方式。如果您先前学习过树链剖分,那么学习树上启发式合并就非常简单了。
首先需要知道一个性质:如果第一行和第一列确定,那么这个方案就已经完全确定了。这个可以用归纳法证明:
证明 如果格子\((i – 1, j)\)、\((i, j – 1)\)和\((i – 1, j – 1)\)的颜色确定,那么显然\((i, j)\)的颜色就能被唯一确定。如果第一行和第一列可以被确定,那么根据上述描述,便可生成一个唯一的方案。
所以欲记录方案的个数,那么就要记录合法的第一行和第一列的方案数。这样我们把问题转换到了长条上。
设置\(dp[i][0/1][0/1]\)为到第\(i\)位是否连续、最后一位填的数字。那么转移非常自然,可以自行推导(确实啊)。
最后答案就是把所有情况加起来,再减去非法的两种情况(也就是左上角的三格同色的情况)。