神题-计算

2018-08-14 16:25:55


给定$n$,求$(x_1,x_2,\dots x_{2m})$的合法方案数。一组$x$是合法的,当且仅当

1.对于任意的$i\in [1,2m]$,有$x_i\in Z^+$且$x_i|n$

  1. $$\prod_{i=1}^{2m}x_i \leq n^m$$

合法的方案数可能有很多,所以输出方案数$mod\ 998244353$的值

看上去完全不可做啊,于是敲完$45$暴力分走人(考场上最高分就是$45$)

其实,这道题的解法非常简单非常神奇

由于$x$可以整除$n$,所以我们可以把条件$2$变一下

$$\prod_{i=1}^{2m}\frac{n}{x_i} \geq n^m$$

我们只考虑$\prod_{i=1}^{2m}\frac{n}{x_i} > n^m$的情况

每一个$\frac{n}{x_i}$,都与之相对应着一个$x_i$,换句话说,如果我们将上式的$\frac{n}{x_i}$替换成$x_i$,会得到相同的方案个数(让新数列的$x_i$取原数列的$\frac{n}{x_i}$即可),这意味着

满足

$$\prod_{i=1}^{2m}x_i < n^m$$

的合法方案个数与满足

$$\prod_{i=1}^{2m}x_i > n^m$$

的合法方案个数相同!

而这两种情况的方案个数和与满足$\prod_{i=1}^{2m}x_i = n^m$的方案个数之和恰好是所有情况(即只满足条件$1$)的方案个数

每个数都可以取值为$n$的因数,一次快速幂就可以计算出所有方案。

对于$\prod_{i=1}^{2m}x_i = n^m$的方案总数,我们把$n^m$想象成很多个球,要放进$x_1,x_2,\dots x_{2m}$这$2m$个箱子里。具体来说:

1.对$n^m$进行分解,不妨设

$$n^m=p_1^{mk_1}p_2^{mk_2}\dots$$

其中,$p_1,p_2,\dots$是质数

然后,对于每个质因数,将$mk$这个幂想象成$mk$个球,要放进$2m$个箱子里,组合数即可。

由于每轮放的球都不一样(分别代表着$p_1,p_2,\dots $),最后将答案乘起来即可,设为$ans$。

最后答案即为$($总方案数$-ans)/2+ans$