主要思路

复盘一年前做过的题，现在感觉确实简单。

考虑表示成 \(d’ \in A, d = d’ + xP\)，然后算有多少个 \(x\) 满足 \(d\) 在 \(B\) 中。暴力直接枚举。考虑优化暴力，我们发现这个肯定是有个循环节的，长度为 \(\text{lcm}(P, Q)\)，这个可以做一个轻微的优化。

我们考虑把这个模 \(Q\) 想成一个环形带，然后把起始位置为 \(start_pos\) 的 \(d \in B\) 在这个纸带上进行标记、做前缀和，为了方便判断前缀和的加减顺序，我们还要标记排名。

计算的时候，对于 \(A_i\)，我们需要知道这个元素 \(T\) 经历了多少次（\(cnt\)）循环，然后完整循环的总和算进去。算完这个之后，我们来算开头和结尾。开头位置肯定就是 \(A_i \bmod Q\)，结尾则是 \((A_i + cnt * P \bmod loop) \bmod Q\)。然后前缀和搞下即可。

暴力算法

有一个比较显然的暴力算法：考虑奇数和偶数长度两种情况，用 BFS 进行同色扩展即可完成。但是复杂度较高，需要实质上 \(\Theta(n^2 + m^2)\) 的时间进行 BFS。

主要思路

这个题是真的难读，读完之后发现就是斯特林数傻逼题。

主要思路

真就二合一？