题解 CF893E 【Counting Arrays】

eee_hoho

2020-11-17 17:27:58

Solution

首先不考虑正负号,那么我们可以把原题看作把$x$的质因子分配到序列的若干个位置中,那么设$x=\prod_ip_i^{k_i}$,则对于每个$p_i$,都有把$k_i$个小球放到$y$个有标号盒子中,并且盒子可以为空,相当于有$k_i+y$个小球放到$y$个有标号盒子中,每个盒子不能为空,于是用插板法解决,方案数为$\begin{pmatrix}k_i+y-1\\y-1\end{pmatrix}$。 然后考虑正负号的问题,我们肯定是每次选择序列中偶数个位置,把他们变为负数,所以有如下式子: $$\sum_{i=0}^{\lfloor\frac{y}{2}\rfloor}\begin{pmatrix}y\\2i\end{pmatrix}$$ 考虑化简这个式子,那么先考虑$y$是奇数,那么有: $$\begin{aligned}\sum_{i=0}^{\frac{y-1}{2}}\begin{pmatrix}y\\2i\end{pmatrix}\\ =\sum_{i=0}^\frac{y-1}{2}\begin{pmatrix}y\\i\end{pmatrix}\end{aligned}$$ 而我们发现$2^y=\sum_{i=0}^y\begin{pmatrix}y\\i\end{pmatrix},\begin{pmatrix}y\\i\end{pmatrix}=\begin{pmatrix}y\\y-i\end{pmatrix}$,那么原式就$=2^{y-1}$。 然后考虑$y$是偶数,那么有: $$\sum_{i=0}^{\frac{y}{2}}\begin{pmatrix}y\\2i\end{pmatrix}$$ 然后如果$\frac{y}{2}$是奇数,那么有: $$\begin{aligned}2\sum_{i=0}^{\frac{\frac{y}{2}-1}{2}}\begin{pmatrix}y\\2i\end{pmatrix}\\=2\sum_{i=0}^{\frac{y}{2}-1}\begin{pmatrix}y-1\\i\end{pmatrix}\end{aligned}\\=2(2^{y-2})=2^{y-2}$$ 而如果$\frac{y}{2}$是偶数,那么有: $$\begin{aligned}2\sum_{i=0}^{\frac{\frac{y}{2}-2}{2}}\begin{pmatrix}y\\2i\end{pmatrix}\end{aligned}+\begin{pmatrix}y\\\frac{y}{2}\end{pmatrix}\\=2\sum_{i=0}^{\frac{y}{2}-2}\begin{pmatrix}y-1\\i\end{pmatrix}+\begin{pmatrix}y\\\frac{y}{2}\end{pmatrix}\\=2(2^{y-2}-\begin{pmatrix}y-1\\\frac{y}{2}-1\end{pmatrix})+\begin{pmatrix}y-1\\\frac{y}{2}\end{pmatrix}+\begin{pmatrix}y-1\\\frac{y}{2}-1\end{pmatrix}\\=2^{y-1}+\begin{pmatrix}y-1\\\frac{y}{2}\end{pmatrix}-\begin{pmatrix}y-1\\\frac{y}{2}-1\end{pmatrix}\\=2^{y-1}$$ 综上所述可以得到$\sum_{i=0}^{\lfloor\frac{y}{2}\rfloor}\begin{pmatrix}y\\2i\end{pmatrix}=2^{y-1}$。 **Code** ``` cpp #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> const int N = 2e6; const int p = 1e9 + 7; using namespace std; int T,x,y,fac[N + 5],inv[N + 5],ans; int mypow(int a,int x){int s = 1;for (;x;x & 1 ? s = 1ll * s * a % p : 0,a = 1ll * a * a % p,x >>= 1);return s;} int C(int n,int m) { return 1ll * fac[n] * inv[n - m] % p * inv[m] % p; } int main() { scanf("%d",&T); fac[0] = 1; for (int i = 1;i <= N;i++) fac[i] = 1ll * fac[i - 1] * i % p; inv[1] = 1; for (int i = 2;i <= N;i++) inv[i] = 1ll * (p - p / i) * inv[p % i] % p; inv[0] = 1; for (int i = 1;i <= N;i++) inv[i] = 1ll * inv[i - 1] * inv[i] % p; while (T--) { scanf("%d%d",&x,&y); ans = mypow(2,y - 1); int xx = x; for (int i = 2;i * i <= xx;i++) if (xx % i == 0) { int cnt = 0; while (xx % i == 0) { xx /= i; cnt++; } ans = 1ll * ans * C(cnt + y - 1,y - 1) % p; } if (xx != 1) ans = 1ll * ans * y % p; printf("%d\n",ans); } return 0; } ```