题解 CF893E 【Counting Arrays】

· · 题解

这里我提供一个数学做法。

我们用C(i,j)代表从j个元素中选择i个元素组成无序元素对的方案数。

首先，考虑安排正负号。由于x是正数，所以最终方案中的y项必然有偶数个负号。

那么，正负号的安排方案共有

$C(0,y)+C(2,y)+C(4,y)+C(6,y)+...+C(y-1,y)$ （$y$是奇数时） 种安排方案。 考虑化简上面的式子。 当$y$是奇数时，有$C(0,y)=C(y,y), C(1,y)=C(y-1,y), ..., C((y-1)/2,y)=C((y+1)/2,y)$。所以我们有$C(0,y)+C(2,y)+C(4,y)+C(6,y)+...+C(y-1,y)=C(1,y)+C(3,y)+...+C(y,y)$。然而注意到$C(0,y)+C(1,y)+C(2,y)+C(3,y)...+C(y,y)=2^y$（组合数基本性质），所以我们有$C(0,y)+C(2,y)+C(4,y)+C(6,y)+...+C(y-1,y)=2^{y-1}$。 当$y$是偶数时，由于$C(i,j)=C(i,j-1)+C(i-1,j-1)$（组合数基本性质），且$C(y,y)=1=C(y-1,y-1)$。所以我们有$C(0,y)+C(2,y)+C(4,y)+C(6,y)+...+C(y,y)=C(0,y-1)+(C(1,y-1)+C(2,y-1))+(C(3,y-1)+C(4,y-1))+...+(C(y-3,y-1)+C(y-2,y-1)+C(y-1,y-1)=2^{y-1}$。 注意上两式结果是一样的，所以我们可以得到正负号的安排方案共有$2^{y-1}$种。 我们将$x$分解质因数，显然我们可以独立考虑每个质因数。设$x=p^dk$，其中$k$不是$p$的倍数。则我们需要将$d$个$p$分给$y$个数。 我们将问题转换为，“将$d$个相同的球放到$y$个不同的盒子里，每个盒子可以为空，问有几种放法。”。这个问题等价于“将$d+y$个球放到$y$个盒子里，每个盒子里有至少一个”。后者又等价于“在$d+y-1$个位置离选$y-1$个位置”。关于这两个问题为什么等价这里不再证明（经典的球与盒子问题）。所以方案数就是$C(y,d)$。 另外最后一个点就是如何$O(1)$计算$C(i,j)$%$mod$的值。由排列组合公式可知$C(i,j)=j!/(i!(j-i)!)$。所以我们可以预处理出$fac[i]$与$inv[i]$，分别代表$(i!)%mod$的值以及$(i!)$的逆元。则$C(i,j)=fac[j]*inv[i]*inv[j-i]$。 注意到预处理inv数组时可以倒着递推，有公式$inv[i]=inv[i+1]*(i+1)$。 这是因为，$fac[i+1]*inv[i+1]=1 => fac[i]*(i+1)*inv[i+1]=1 => fac[i]*((i+1)*inv[i+1])=1$。 于是此题得解，代码很好写，就不放了。