CF396
CF396A
CF396A题意
给出一个长度为 \(n\) 的序列 \(a\),令 \(m=\prod_{i=1}^na_i\),问有多少个长度为 \(n\) 的序列使得序列中的所有数的乘积等于 \(m\)。
CF396A题解
首先质因数分解,可以证明,最多的质因数不会超过 \(500\times \log_210^9=14949\),于是可以快乐预处理。
然后对于每一个质因数,设它在原数组中有 \(k_i\) 个,那么相当于在 \(n\) 个有顺序的盒子中放入 \(k_i\) 个相同的小球,每个盒子可以不放或者放多个。很显然方案数是 \({n+k_i-1\choose n-1}\) 个。用不到 Lucas
定理。
CF396A代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x = 0, f= 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 1e5 + 10, mod = 1e9 + 7;
int n;
int prime[maxn], tot;
bool book[maxn];
unordered_map<int,int> mp;
int pw[maxn], invpw[maxn];
int qpow(int x,int a){
int res = 1;
while(a){
if(a & 1)res = res * x % mod;
x = x * x % mod;a >>= 1;
}
return res;
}
int C(int n,int m){return pw[n] * invpw[m] % mod * invpw[n - m] % mod;}
signed main(){
n = read();pw[0] = 1;pw[1] = 1;
for(int i = 2;i <= 1e5;i++){
pw[i] = pw[i - 1] * i % mod;
if(!book[i])prime[++tot] = i;
for(int j = 1;j <= tot && prime[j] * i <= 1e5;j++){
book[i * prime[j]] = 1;
if(i % prime[j] == 0)break;
}
}
invpw[(int)1e5] = qpow(pw[(int)1e5],mod - 2);
for(int i = 1e5 - 1;i + 1;i--){invpw[i] = invpw[i + 1] * (i + 1) % mod;}
for(int i = 1;i <= n;i++){
int x = read();
for(int j = 1;j <= tot;j++)
while(x % prime[j] == 0){
mp[prime[j]]++;x /= prime[j];
}
if(x != 1)mp[x]++;
}
int ans = 1;
for(auto it = mp.begin();it != mp.end();it++){
// printf("it = %lld\n",it->second);
ans = ans * C(n + (it->second) - 1,n - 1) % mod;
}
printf("%lld\n",ans);
return 0;
}