Codeforces 893E - Counting Arrays

Author Avatar
Jimmy Zhang Jul 14, 2018
  • Read this article on other devices

题面

对于正整数 xxyy,求有多少种长度为 yy 的序列,其元素的乘积为 xx。序列中允许出现负数,对于两个序列 aabb 只要存在 aibia_i \neq b_i 就视作两个不同序列。答案对 109+710^9 + 7 取模。

数据范围

一组数据有 qq 次询问,1q1051 \le q \le 10^5

1x,y1061 \le x,y \le 10^6

题目链接

组合数学

思路

首先,我们对 xx 分解质因数:
x=p1k1p2k2pnknx = p_1^{k_1} \cdot p_2^{k_2} \cdot \dots \cdot p_n^{k_n}

同时,我们知道序列中的任意一个值 aia_i 一定可以表示为如下形式:
ai=p1t1p2t2pntna_i = p_1^{t_1} \cdot p_2^{t_2} \cdot \dots \cdot p_n^{t_n}
现在我们先暂且不考虑负数的情况。我们把质因子视作“小球”,序列中的每一个元素视为“箱子”。由此我们可以把问题转换为经典的“球放箱子”问题:现有 nn 类小球,第 ii 类小球有 kik_i 个,同时有 yy 个箱子,箱子可以为空,试问把所有小球放到箱子里有多少种放法。

对于第 ii 类小球,一共有 kik_i 个,同时一个箱子可以放多个。这等效于一共有 y+ki1y + k_i - 1 个箱子且每个箱子最多放一个小球。因此摆放种数为:
(y+ki1ki)\binom{y + k_i - 1}{k_i}

根据乘法原理,所有小球的总摆放种数为:
i=1n(y+ki1ki)\prod_{i = 1}^{n} \binom{y + k_i - 1}{k_i}

接下来,我们来考虑负数。显然,在序列中,y1y - 1 个数的正负可以是任意的,而乘积的正负可以由剩下的那一个数来决定。所以,总拜访种数为:
2y1i=1n(y+ki1ki)2^{y - 1} \cdot \prod_{i = 1}^{n} \binom{y + k_i - 1}{k_i}

实现

这道题思路是可以说是非常简单,但是看看数据范围就知道在实现上需要运用一些技巧。

首先,在对 xx 分解质因数前需要先线性筛素数,分解质因数时应尽量“剪枝”。

在求组合数时复杂度应做到 O(1)\mathcal{O}(1),因此需要预处理 n!n! 及其对于 109+710^9 + 7 逆元。

最后,还要预处理 22 的幂。

另外在做这道题的过程中顺便学到了一种线性预处理逆元的算法,但这道题用不到。为了试试这种算法,第一份参考代码中使用了这一算法来预处理逆元。

完整参考代码 - 1

完整参考代码 - 2

%%%

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/07/13/codeforces-893e/