题目链接:Codeforces 396A On Number of Decompositions into Multipliers
题目大意:给出n个数,ai,然后取这n个数的积为m,计算将m分解成n个因子,问有多少种有序因子序列。
解题思路:n为500,ai的上限为1e9,所以要表示m是完全不可能的,但是记录下m的因子个数是完全可以的,因为ai就是m的因子,所以把ai分解成质因子然后离散保存个数。
接下来枚举每种因子的分配情况,假如因子t有k个,那么将k个因子分配到n个位置的方式数即为C(k+n-1, n-1),这是组合数学中的隔板法,要将m个糖果分成n份的方法数即为C(m-1,n-1),即将糖果排成一排,然后枚举任意两个糖果之间放一个隔板,(这样会保证说每一份都会有至少一个糖果,但是这道题有点不同,有些数可能没有分到这个因子);k+n-1个位置,选n-1个位置放隔板,其他的就是因子,然后每两个板之间的因子个数就对应着某个数含有该因子的个数。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <map>
using namespace std;
typedef long long ll;
const int N = 17000;
const int M = 1000;
const int mod = 1e9+7;
int n, k;
ll c[N][M];
map<int, int> g;
void init () {
c[0][0] = 1;
for (int i = 1; i < N; i++) {
for (int j = 0; j <= i && j < M; j++) {
if (j == 0 || j == i) c[i][j] = 1;
else c[i][j] = (c[i-1][j-1] + c[i-1][j])%mod;
}
}
}
void solve (ll k) {
for (int j = 2; j * j <= k; j++) if (k % j == 0) {
int cnt = 0;
while (k%j == 0) {
k /= j;
cnt++;
}
g[j] += cnt;
}
if (k > 1) g[k] += 1;
}
int main () {
init();
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &k);
solve(k);
}
ll ans = 1;
for (map<int, int>::iterator i = g.begin(); i != g.end(); i++) {
int t = (*i).second;
ans = (ans * c[t+n-1][n-1]) % mod;
}
cout << ans << endl;
return 0;
}
分享到:
相关推荐
Codeforces 185A - Plant 全测试点49个
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
Some of the Codeforces problems codes
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
Codeforces global round 10 codes
Codeforces round 678 division 2 codes
接受串子-接受字符串相等-接受Codeforces回合#684(Div.2) 2/6 1440A-购买琴弦-接受1440B -中位数的总和-已接受1440C1-二进制表(简易版)-已接受1440C2-二进制表(硬版)-已接受 Codeforces回合#683(分区2) 1/...
codeforces每日一题。 题意: 给出一个数组,让你挑选出能组成任意pair差值为2的幂的序列,并且使这个序列长度尽可能大。 思路: 针对于挑选出来的序列,任意pair对的差值为2的幂数。 假设有多个pair对,设dis(a,b)=2...
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done
Codeforces round 678 D2_Codeforces_源码
打codeforces的神器
一个Codeforces、牛客竞赛、AtCoder平台的编程竞赛查询插件,ACMer必备.zip
codeforces-js Codeforces JS
使用 C# + WPF 开发 --- 还在发愁打了那么多场比赛都没有进入首页么? 还在为了前 5 的 hacker 名额阅读千份代码么? 是的,你没有看错! 这是一个 Edu & Div.3 轮 Open hacking 错误代码自动查找器!...
Codeforces Round #723 (Div. 2).md
codeforces算法比赛题:1295A题
Codeforces 题库 201-294 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。