8.27 做题笔记

\(\text{A}\)

题目链接

我们思考什么时候 \(n\) 满足 \(D(k\times n)=k\times D(n)\)。如果 \(n\) 乘 \(k\) 没有进位，显然满足条件。除此之外，我们可以证明数位和一定小于 \(k\times D(n)\)。得到结论后，我们再次思考 \(n\) 乘 \(k\) 没有进位的情况，显然所有数位 \(x\times k\leq 10\)，所以我们不妨枚举这个数字 \(ma=\lceil\frac{10}{k}\rceil\)，如果 \(k>10\) 直接输出 \(0\) 即可。

随后，我们考虑使用计数题常用技巧，把问题转化成定义 \(f(i)\) 表示 \(1\sim i\) 位下可能的答案，求 \(f(r)-f(l)\)。显然每一个数位都可以在 \(0\sim ma-1\) 中任意选择，即为 \(ma^i\)，直接求 \(ma^r-ma^l\) 即可。

\(\text{B}\)

题目链接

我们不妨考虑区间的最小值为 \(mi\)，最大值为 \(ma\) 的可能方案数，定义长度为 \(len\)，显然我们可以把这个长度为 \(ma-mi+1\) 的区间有可能的 \(n-len+1\) 中起点，在区间内部，因为出现的只有 \(l\sim r\) 且所有数字不同，有 \(len!\) 种排列方案，在区间外部，有 \((n-len)!\) 种排列方案，因此贡献是 \((n-len+1)(len!)((n-len)!)\)。

显然所有长度相同的区间贡献相等，对于长度为 \(len\) 的长度，有 \(n-len+1\) 种可能的 \([mi,ma]\)。因此答案如下，预处理阶乘即可：

\[\sum^{n}_{len=1}(n-len+1)^2(len!)((n-len)!) \]

\(\text{C}\)

题目链接

我们考虑分类讨论。

显然如果有一对 \(a_l\) 与 \(a_r\) 对 \(m\) 同余，答案为 \(0\)。

如果 \(n\geq m\)，根据抽屉定理，一定有一对 \(a_l\) 与 \(a_r\) 模 \(m\) 余数相等，即对 \(m\) 同余。否则 \(n\leq m\leq 10^3\)，暴力模拟寻找答案即可。

我们也可以将 \(a\) 排序后发现对于 \(a_i\)，在它前面的模 \(m\) 相同的数与其差是相等的。所以我们枚举每个余数，统计每种差出现的次数 \(f(i)\)，最后使用快速幂相乘即可。