阅读 65

On Number of Decompositions into Multipliers CodeForces - 396A


考察:组合数学
错误思路:
??隔板法忘光了,没做出来= =
思路:
??很容易想到是分解质因数,然后将质因数安排在\(n\)个位置上.这里比较容易想到隔板法,但是注意常规隔板法是需要\(x_i>=1\),所以我们需要将\(x_i+n-1\).还有一个就是质因数排序问题,注意到案例三\(5,7\)做一次隔板少了\(7,5\)这一种情况.将质因数分类考虑,每个做隔板法再相乘即可.

Code

#include  
#include 
#include 
using namespace std;
typedef long long LL;
const int N = 510,M = 1000000007,S = 20010;
int a[N],n;
map 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

原文：https://www.cnblogs.com/newblg/p/15302960.html
文章分类
代码人生
文章标签
on
number
of
decompositions
into
multipliers
codeforces
版权声明：本站是系统测试站点，无实际运营。本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 XXXXXXo@163.com 举报，一经查实，本站将立刻删除。
相关推荐