首页 > ACM题库 > HDU-杭电 > HDU 4390-Number Sequence-组合数学-[解题报告]HOJ
2015
05-24

HDU 4390-Number Sequence-组合数学-[解题报告]HOJ

Number Sequence

问题描述 :

Given a number sequence b1,b2…bn.
Please count how many number sequences a1,a2,…,an satisfy the condition that a1*a2*…*an=b1*b2*…*bn (ai>1).

输入:

The input consists of multiple test cases.
For each test case, the first line contains an integer n(1<=n<=20). The second line contains n integers which indicate b1, b2,…,bn(1<bi<=1000000, b1*b2*…*bn<=1025).

输出:

The input consists of multiple test cases.
For each test case, the first line contains an integer n(1<=n<=20). The second line contains n integers which indicate b1, b2,…,bn(1<bi<=1000000, b1*b2*…*bn<=1025).

样例输入:

2
3 4

样例输出:

4
Hint
For the sample input, P=3*4=12. Here are the number sequences that satisfy the condition: 2 6 3 4 4 3 6 2

题目:Number Sequence


#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
typedef long long LL;

const int N=1000005;
const LL MOD=1000000007;

int p[N];
int a[N],b[N];
bool prime[N];
LL C[1005][1005];
int k;

void isprime()
{
    int i,j;
    k=0;
    memset(prime,true,sizeof(prime));
    for(i=2; i<N; i++)
    {
        if(prime[i])
        {
            p[k++]=i;
            for(j=i+i; j<N; j+=i)
            {
                prime[j]=false;
            }
        }
    }
}

void Init()
{
    int i,j;
    for(i=0; i<1005; i++)
    {
        C[i][0]=C[i][i]=1;
        for(j=1; j<i; j++)
        {
            C[i][j]=(C[i-1][j]%MOD+C[i-1][j-1]%MOD)%MOD;
        }
    }
}

void Solve(int b[],int n)
{
    memset(a,0,sizeof(a));
    for(int i=0; i<n; i++)
    {
        for(int j=0; p[j]<=b[i]; j++)
        {
            if(b[i]%p[j]==0)
            {
                while(b[i]%p[j]==0)
                {
                    a[j]++;
                    b[i]/=p[j];
                }
            }
        }
    }
}

int main()
{
    isprime();
    Init();
    LL ans,n;
    while(~scanf("%I64d",&n))
    {
        ans=0;
        for(int i=0; i<n; i++)
            scanf("%d",&b[i]);
        Solve(b,n);
        
        for(int i=0; i<n; i++)
        {
            LL tmp =C[n][i];
            for(int j=0; j<k; j++)
                tmp=(tmp*C[a[j]+n-i-1][a[j]])%MOD;
            ans+=(i&1)?-tmp:tmp;
            ans%=MOD;
        }
        printf("%d\n",(ans%MOD+MOD)%MOD);
    }
    return 0;
}


版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acdreamers/article/details/9735125