神题-计算

· · 个人记录

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

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

2.\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