On Number of Decompositions into Multipliers CodeForces - 396A
2021/9/17 6:04:55
本文主要是介绍On Number of Decompositions into Multipliers CodeForces - 396A,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
原题链接
考察:组合数学
错误思路:
隔板法忘光了,没做出来= =
思路:
很容易想到是分解质因数,然后将质因数安排在\(n\)个位置上.这里比较容易想到隔板法,但是注意常规隔板法是需要\(x_i>=1\),所以我们需要将\(x_i+n-1\).还有一个就是质因数排序问题,注意到案例三\(5,7\)做一次隔板少了\(7,5\)这一种情况.将质因数分类考虑,每个做隔板法再相乘即可.
Code
#include <iostream> #include <cstring> #include <map> using namespace std; typedef long long LL; const int N = 510,M = 1000000007,S = 20010; int a[N],n; map<int,int> mp; LL fact[S],infact[S]; void GetDivide(int n) { for(int i=2;i<=n/i;i++) { if(n%i==0) while(n%i==0) n/=i,mp[i]++; } if(n>1) mp[n]++; } int qsm(int a,int k,int m) { int res = 1; while(k) { if(k&1) res = (LL)res*a%m; a = (LL)a*a%m; k>>=1; } return res; } void init() { fact[0] = 1,infact[0] = 1; for(int i=1;i<S;i++) { fact[i] = (LL)fact[i-1]*i%M; infact[i] = (LL)infact[i-1]*qsm(i,M-2,M)%M; } } LL C(int a,int b) { if(a<b) return 0; return fact[a]*infact[b]%M*infact[a-b]%M; } int main() { scanf("%d",&n); init(); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); GetDivide(a[i]); } int res = 1; for(auto& it:mp) { int x = it.second; res = (LL)res*C(x+n-1,n-1)%M; } printf("%d\n",res); return 0; }
这篇关于On Number of Decompositions into Multipliers CodeForces - 396A的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享