abc293 题解

A/B

按题意模拟即可。
A
B

C

注意到共要走 $H+W-1$ 步，每步有两个方向可选，共 $2^{H+W-1}$ 种情况。
由于 $2\le H,W\le 10$ ，故 $H+W-1\le 19$ ，故爆搜即可。
C

D

显然的，颜色在本题中是无效的变量，实际题意如下：

给定一张无向图，保证任意一点度不超过 $2$ ，无重边、自环，
求环的数量和非环的连通块数。

其实已经可以 $DFS$ 了，但我不想写，所以再观察下。

由于任意一点度不超过 $2$ ，因此连通块只有点、链、环三种可能。
其中，满足每个点度数都为 $2$ 的联通块才是环。
因此考虑并查集，对于每个点维护度数，最后再求出每个连通块的点的最小度数即可。
D

E

首先考虑暴力。设 $f(x)=\sum_{i=0}^{x-1}a^i$ ，
则有 $f(x)=f(x-1)\times x+1$ ，边界值 $f(0)=1$
此时发现 $f(x)$ 的值仅和 $f(x-1)$ 有关，因此考虑到矩阵快速幂。
我们可以对 $f$ 构造如下矩阵：

$$\begin{bmatrix}f(x)\\1\end{bmatrix}$$

则每次递推相当于乘上如下矩阵:

$$\begin{bmatrix}a&1\\0&1\end{bmatrix}$$

每次乘完 $\bmod\ M$ 即可。

题目至此已经解决了
吗？

交上去，会发现 $\rm WA\times 2$ 。。。
问题在哪？

在 边界值 $f(0)=1$ 。
因为原题数据范围为 $1\le M\le 10^9$
因此还要特判 $M=1$ 的情况。。。
E 和 四发罚时

F

好像是有结论的？
不重要。
暴力可以解决一切~

注意到对于不同进制 $b$ ，$n$ 的 $b$ 进制表示法显然不同，
可以得出以下两种暴力：

1. 枚举进制 $b$ ，判断 $n$ 的 $b$ 进制表示法是否只由 $1$ 和 $0$ 构成，时间复杂度 $O(n\log n)$
2. 枚举 $n$ 的表示法，二分是否有满足此表示法的 $b$ 。看似更优了，可时间复杂度仍为 $O(2^{\log n}\log n)=O(n\log n)$ 。

此时已经可以通过 $n\le 1000$ 左右，我们接着考虑 $n>1000$ 时的做法。

接着，我们发现对于第一种暴力，当进制 $b> \sqrt n$ 时，有且仅有 $n$ 和 $n-1$ 两种答案。从第二个暴力的角度，我们发现当 $b> \sqrt[4]n$ 时 $n$ 最多只有以下 $14$ 种表示法：
10,11,100,101,110,111,1000,1001,1010,1011,1100,1101,1110,1111，因此考虑将两种暴力结合，先使用第二种暴力判段以上 $14$ 种表示方法，再使用第一种方法枚举 $d\le \sqrt[4]n$ 的情况，复杂度为 $O(n \sqrt[4]n\log n)$ ，已经可以通过此题。
若是将特判扩大更多以寻找平衡点可以有更优的复杂度，此处不在讨论。
F
PS：一定要处理好二分边界!

G

一眼莫队。
具体的，一个点加入区间的贡献为增加的同颜色三元组数，由于这个点加在边界处，贡献即为加入前已有点的两元组数，为
$\sum_{i=1}^{cnt_x}cnt_x-i=\frac{(cnt_x-1)\times{cnt_x}}{2}$
删除时同理。
G
PS：一定是 $q$ 组询问，不是 $n$ 组！一定是 $q$ 组询问，不是 $n$ 组！一定是 $q$ 组询问，不是 $n$ 组！……

Ex

感觉是换根 $dp$ ？还没做出来，待会来补。