ARC160

B

考虑题目的三个条件，只需要满足最大的两个数的乘积小于等于 \(n\) 。\(x,y,z\) 的大小关系无所谓，分讨两种情况 \(x=y\ge z\) 和 \(x>y\ge z\)，分别枚举 \(x,y\) 即可，复杂度 \(\mathcal{O}(T\sqrt{n})\)

C

计数，本来是对 \(a\) 计数，不好做，考虑 换元转化 。设 \(c_i\) 表示 \(i-1\) 到 \(i\) 贡献了多少，转化为对不同 \(c\) 计数。那么有 \(a_{i-1}+c_{i-1}\ge 2c_{i}\)，得到 \(c_{i-1}\ge 2c_i-a_{i-1}\)，是个后缀和。设 DP \(f_{i,j}\) 表示 \(c_i=j\) 的方案数，容易发现一个数的贡献是 \(1+\frac{1}{2}+\dots\)，总共 \(n\) 个数，不超过 \(\mathcal{O}(n)\) 级别，总复杂度 \(\mathcal{O}(n)\)

总结：计数，一般考虑 换元转化

D

合法序列 \(a\) 不好计数，转化为对操作序列计数。考虑如何构造双射。关注 顺序，发现顺序无关，考虑两个操作序列等价的 条件，对比可知，必然是不同操作的影响等价，容易发现对于 \(i\) 操作 \(k\) 次操作 \(2\) 等价于对 \([i,i+k-1]\) 分别操作 \(1\) 次操作 \(1\) 。那么设 \(b_i\) 表示 \(i\) 操作多少次操作 \(2\)，那么钦定 \(b_i<k\)，那么不同操作就不可能相互转化，也就不可能出现两个不同的等价操作序列。设 \(g_i\) 表示 \(i\) 操作多少次操作 \(1\)，那么有 \(\forall\;i,b_i<k\) 和 \(\sum b+g=\dfrac{m}{k}\)，对于第一个条件进行容斥，第二个条件进行插板法即可。

总结：计数，一般考虑 换元转化