Codeforces396A - On Number of Decompositions into Multipliers
Description
给出\(n(n\leq500)\)个\([1,10^9]\)的数,令\(m=\prod_{i=1}^n a_i\)。求有多少个有序排列\(\{a_n\}\),使得\(\prod_{i=1}^n a_i=m\)。答案\(mod \ 10^9+7\);两个有序排列不同当且仅当\(\exists i,a_i \neq b_i\)。
Solution
将\(m\)分解质因数,即\(m=\prod_{i=1}^t p_i^{k_i}\)。
将\(m\)分配到\(n\)个数上,相当于依次将\(k_i\)个\(p_i\)分配到\(n\)个数上。因为\(p_i\)均不相同,所以不会出现重复的计算。即:
> 时间复杂度$O(?)$,分解质因数复杂度怎么算呀...
##Code
```
//On Number of Decompositions into Multipliers
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
typedef long long lint;
int const N0=1e5+10;
lint const H=1e9+7;
map<int,int>::iterator it;
map<int,int> cnt;
bool isP[N0]; int cntP,P[N0];
lint C[15000][510];
void init()
{
memset(isP,true,sizeof isP);
for(int i=2;i<=1e5;i++)
{
if(isP[i]) P[++cntP]=i;
for(int j=1;j<=cntP;j++)
{
if(i*P[j]>1e5) break;
isP[i*P[j]]=false;
if(i%P[j]==0) break;
}
}
for(int i=0;i<15e3;i++) C[i][0]=1;
for(int i=1;i<15e3;i++)
for(int j=1;j<=i&&j<=500;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%H;
}
int n;
int main()
{
init();
scanf("%d",&n);
for(int owo=1;owo<=n;owo++)
{
int x; scanf("%d",&x);
for(int i=1;i<=cntP;i++)
while(x%P[i]==0) cnt[P[i]]++,x/=P[i];
if(x!=1) cnt[x]++;
}
lint ans=1;
for(it=cnt.begin();it!=cnt.end();it++) ans*=C[it->second+n-1][n-1],ans%=H;
printf("%lld\n",ans);
return 0;
}
```
##P.S.
我VisJiao就是打死,也不吃STL一口饭!
...真香\]
最新文章
- 分享Kali Linux 2016.2第50周镜像文件
- MySQL JDBC 出现多个 SHOW VARIABLES 语句。
- 微信token验证失败的解决方法
- SharePoint 2010 文档管理之文档推送
- Linux运维工程师入门须掌握的10个技术点
- Maven错误在这里看【项目无法成功编译由于maven未成功下载依赖导致】
- hdu 2255 奔小康赚大钱 KM算法
- plsql developer 使用技巧
- [视频监控]用状态机图展示Layout切换关系
- java中对于JSON 的处理 fastjson gson 系统自带的JSON 的选择
- stm32基础入门
- ubuntu 系统 更改屏幕亮度为最大(15级亮度)
- Retrofit网络请求库应用02——json解析
- 可变有序列表list
- Windows 不能在本地计算机启动 OracleDBConsoleorcl的问题解决方法
- Go语言流程控制
- U-BOOT2016.05 配置内存大小
- 监督学习Supervised Learning
- 云计算之 PaaS详解
- 白盒测试实践-day....