1000:MegaFactorialDiv2

题意:

题目给出一种数字表达方式,n!k。。。并且满足如下条件:

  1. n!k = n!(k-1) * (n-1)!k for n > 0 and k > 0
  2. n!k = 1 for n = 0
  3. n!k = n for k = 0

然后题目给出一个N和K,让你输出N!K。。。

分析:

  • 4!0 = 4
  • ————————————————————-
  • 4!1 = 4!0 * 3!0 * 2!0 * 1!0
  • = 4!
  • = 4 * 3 * 2 * 1
  • ————————————————————-
  • 4!2 = 4!1 * 3!1 * 2!1 * 1!1
  • = (4 * 3 * 2 * 1) * (3 * 2 * 1) * (2 * 1) * 1
  • = (4) * (3*3) * (2*2*2) * (1*1*1*1)
  • ————————————————————-
  • 4!3 = 4!2 * 3!2 * 2!2 * 1!2
  • = (4!1 * 3!1 * 2!1 * 1!1) * (3!1 * 2!1 * 1!1) * (2!1 * 1!1) * (1!1)
  • = (4!1) * (3!1)^2 * (2!1)^3 * (1!1)^4
  • = 4*3*2*1 * (3*2*1)^2 * (2*1)^3 * (1*1*1*1)
  • = (4) * (3*3*3) * (2*2*2*2*2*2) * (1*1*1*1*1*1*1*1*1*1)
  • = 41 * 33 * 26 * 110

我们先打了一波表,可以发现如下规律:

可以看出 N!K = N^f(N,N,K) * (N-1)^f(N-1,N,k)*…X^f(X,N,K)…2^f(2,N,K)*1^f(1,N,K),f(X,N,K) 表示X在N!K连乘中出现的次数, 1<=X<=N, 当X>N时, f(X, N, K) = 0。

例如 4!1= 4!= 4 * 3* 2 *1,则f(4,4,1)= 1,f(X,N,1) = 1;

4!3 = 41 * 33 * 26 * 110, 则f(3,4,3) = 3, f(2,4,3) = 6.

因为n!k = n!(k-1) * (n-1)!k, 所以f(X,N,K) = f(X, N, K-1) + f(X, N-1, K).

f(X,1,k) = 0;(2<=X=N, 1<= k <=K)

f(X,n, 1) = 1(1<= n <=N; x<=n), f(X, n, 1) = 0(x > n )

可以递推求得f(X,N,K)值,时间复杂度O(X*N*K), 因为X<=N,所以为O(N^2*K)。

其实对于公式f(X,N,K) = f(X, N, K-1) + f(X, N-1, K)来说,X值并不改变,f(x, n, k) = f(x+1, n+1, k)= f(x+T, n+T, k)

这样只需要计算出f(2, n, k), f(x,n,k) = f(2, n-x+2, k), 这样时间复杂度降至O(N*K).

—————————————————————-

对于一个正整数n, 怎样求其因子个数之和? 假设n = p1^e1 * p2^e2*…*pt^et,则因子个数之和= (e1+1)*(e2+1)*…(et+1)。其中pi表示小于等于n的所有素数。

然后我们只要求出F(2,n,k)就好了对吧。。。

代码:

LL f[1010][101];
LL add[1010],ans;
int MegaFactorialDiv2::countDivisors(int N, int K) {
	ans=1;
	memset(add,0,sizeof(add));
	memset(f,0,sizeof(f));
	for(int i=2;i<=N;i++)
		f[i][1]=1;
    for(int i=1;i<=N;i++)
		for(int j=2;j<=K;j++)
			f[i][j]=(f[i-1][j]+f[i][j-1])%mod;
	for(int i=1;i<=N;i++)
	{
		LL flag=f[N-i+2][K],zz=i;
		for(int j=2;j<=sqrt(zz);j++)
			if(zz%j==0)
			{
				int sum=0;
				while(zz%j==0)
					zz/=j,sum++;
				(add[j]+=sum*flag+mod)%=mod;
				if(add[j]<0)add[j]+=mod; 			} 		if(zz>1)
		{
			(add[zz]+=flag)%=mod;
			if(add[zz]<0)add[zz]+=mod;
		}
	}
	for(int i=1;i<=N;i++)
		(ans*=(add[i]+1))%=mod;
	return ans;
}

 

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注