A - Integer Product
由于每一个数都可以表示为十进制下的有限小数，所以化成分数后其分母的只可能含有 \(2\) 和 \(5\) 两个质因子。记录其次数，那么就是求 \(2\) 和 \(5\) 的次数加起来都大于等于 \(0\) 的数对个数。这个可以开一个桶暴力计算。
为了方便，一开始把每个数都乘上 \(10^9\)，这样求的就是次数加起来大于等于 \(18\) 的数对个数。复杂度 \(O(n\log^2n)\)。
B - First Second
不难发现，如果 \(T\) 能从 \(S\) 得到，那么 \(T\) 一定可以表示为 \(S\) 中的一个字符拼上 \(S\) 的一个后缀（可以为空后缀，字符必须在后缀前）。
考虑用 Trie 树，我们每一次倒着插入一个 \(S_i\)，额外开一个数组 sum[x][c] 记录 \(x\) 的子树内字符 \(c\) 的出边数量，这样每走一步我们都看一下 \(S\) 前面的字符种类，如果有把 sum[x][c] 对应加上 1，全插入完以后再查询一下就做完了。复杂度 \(O(26\sum|S|)\)。上述操作也可以通过哈希完成，但是我一开始写的哈希跑的太慢了过不去。
C - Product Modulo
我们发现模数很小而且是质数，所以我们考虑计算 \(A_iA_j=c\) 的 \((i,j)\) 的数量。因为是质数，存在原根（温馨提示 \(200003\) 的一个原根是 \(5\)），所以我们可以把每一个数都取离散对数，那么乘法就变成了加法，这样可以通过 FFT 快速计算（注意不能用单模 NTT 可能会爆）。复杂度 \(O(n+p\log p)\)。
D - Twin Binary Trees
首先我们发现如果我们确定了两条特殊边，那么我们就唯一确定了一条回路。我们考虑枚举这条回路在第一棵树上的 LCA，那么所有的回路在第一棵树上的叶子一定分别在两个子树内。
我们设两棵子树分别为 \(L\) 和 \(R\)，我们先枚举 \(L\) 中的每个叶子，然后我们参照 LNOI LCA 那道题的套路，把第二棵树中对应叶子（通过特殊边连接的）到第二棵树上的根上的每个节点加上从枚举的 LCA 到这个节点的编号乘积。然后我们枚举 \(R\) 中的叶子，并从第二棵树中对应的叶子向上跳，那么每当我们跳到一个点 \(x\) 时，在第二棵树的 LCA 为这个点的所有回路的总贡献为 \(\text{dis}(LCA,x)\cdot(w[x]-x\cdot w[pre])\)，其中 \(pre\) 是上一个经过的点，\(w\) 是点上的权值， \(\text{dis}\) 为 LCA 到 \(x\) 路径点的乘积（不含端点），要减去 \(x\cdot w[pre]\) 是因为要减去 LCA 已经被算过的部分。这样总复杂度为 \(O(H^22^H)\)。
E - Product Simulation
我们考虑把 \(A,B\) 分解成二进制后再乘。一共要干三件事：预处理 \(2\) 的次幂；提取出 \(A,B\) 在二进制中的每一位；二进制下乘法。
可以发现 \(A=B=0\) 怎么操作都是 \(0\)，所以下面均讨论 \(A,B\) 至少有一个不是 \(0\) 的情况。
注意到一定有 \(A<2A+2B\)，所以可以得到 \(1\)，然后就可以处理出 \(2\) 的次幂。
考虑如何分解，我们从高向低位 for，设当前处理到第 \(i\) 位，只考虑更高位时 \(A\) 的值为 \(nowa\)，如果这一位为 \(1\) 则有 \(nowa+2^i\leqslant A\)，即 \(nowa+2^i<A+1\)。注意求出这一位的值以后我们需要花 \(O(\log A)\) 的时间通过计算好的每一位的值重新计算 \(nowa\)。对于 \(B\) 同理。这一部分的复杂度是 \(O(\log^2A)\)。
接下来考虑二进制下的乘法，设 \(fa_i\) 为 \(A\) 的二进制表示下第 \(i\) 位的值，\(fb_i\) 同理，则： \[ AB=\sum\limits_{i.j}fa_ifb_j2^{i+j} \] 注意到 \(fa_i,fb_j\) 都是 \(0,1\) 变量，故 \(fa_ifb_j=[1<fa_i+fb_j]\)，这样枚举 \(i,j\)，然后把\(fa_ifb_j\)连续左移 \(i+j\) 次就是这两位的贡献，这样的复杂度是 \(O(\log^3A)\)。
我们可以转换思路枚举 \(i+j\)，我不是很会用语言描述，所以直接贴一个官方题解给出的代码，相信很好看懂：
1 | for(int k = 58; k >= 0; k--) { |
这个的复杂度是 \(O(\log^2A)\)。
F - Rooks
先考虑 \(O(n^2)\) 的 dp。
不难发现按 \(x\) 排序之后每个点能到达的一定是一个区间。设 \(f(l,r,0/1)\) 表示从 \([l,r]\) 这个状态到无法继续扩展的状态的最小步数，转移只需枚举下一步走哪里。从 \(i\) 开始的答案就是 \(f(i,i,0)\)。
我们考虑一种特殊情况：给定的 \(x\) 和 \(y\) 单调。不难发现从任何点出发都可以吃掉所有车，而且最短路一定是一路吃到 \(1\) 再去吃 \(n\) 和反过来的较小值。
我们可以发现如果从点 \(i\) 去吃点 \(j\)，花费的步数是 \(dis(i,j)-1\)（这里是曼哈顿距离），为了方便，我们计算时把代价认为是 \(dis(i,j)\)，最后再减掉吃的车的个数。
有了这种情况我们发现上面那个 \(O(n^2)\) 的 dp 有很多无用的状态（因为你来回吃一定不如先一直吃一头再回来），可以优化。
我们令 \(L_i\) 表示从 \(i\) 向左出发，保证走过的纵坐标也是连续且单调，最远能走到哪，\(R_i\) 类似。那么我们发现从 \([l,r]\) 只需要转移到 \([L_{l-1},r]\) 和 \([l,R_{r+1}]\)，否则根据上面那个贪心一定不优。
（不保证以下内容正确）这样我们访问到的区间个数是线性的，由于实现用了 map 所以是 \(O(n\log n)\) 的。