hdu 4390

링크:http://acm.hdu.edu.cn/showproblem.php?pid=4390
n 개 줄 게 (n < = 20), b1, b2,... bn, a1, a2,........................................................... ，그리고 모든 ai 는 1 보다 커 야 합 니 다.
데이터 범위 1000 도 가능 합 니 다.
딱 봐 도 조합 문제 이다. 우선, 첫 번 째 단 계 는 질 인 수 를 먼저 분해 한 다음 에 하나의 배열 a 를 얻 는 것 이다. a [i] 는 i 번 째 소수 의 개 수 를 나타 내 는데 이 소수 가 무엇 인지 이미 중요 하지 않다.
그 다음 에 각 소 수 를 n 개의 용기 에 차례대로 넣 고 각 소수 에 각각 얼마나 넣 는 지 기록 하 는 것 과 같다. tot 종 소수 f (i) 가 i 종 소 수 를 나타 내 는 방 법 이 있다 고 가정 하면 n 개 수 중 일부 가 1 이 될 수 있다. 즉, n 개 용기 의 일부 위 치 는 놓 지 않 아 도 된다. 전체적인 방안 은 f (1) * f (2) *.용 척 원리 로 할 수 있다. 즉, 현재 구 하 는 총 방안 수 에서 용기 하나 에 0 을 두 는 방안 수 를 빼 고 두 개의 위치 에 0 을 두 는 방안 수 를 더 하면 적어도 세 개의 위치 에 0 을 두 는 방안 수 를 빼 고...
이렇게 얻 은 것 이 답 이다.
m 개 수 를 n 개 용기 에 넣 으 면 n - 1 개의 칸막이 가 있 는 셈 이다. 전체적인 방안 은 C (n - 1, n + m - 1) 이다.

#include<cstdio>
#include<cmath>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod = 1000000007;
int C[1000][1000];
vector<int> p;
void init(){
    for(int i=0;i<1000;i++){
        C[i][0]=1;
        C[i][i]=1;
        for(int j=1;j<i;j++){
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
        }
    }
}
void make(int num){
    for(int i=2;i*i<=num;i++){
        if(num%i==0){
            while(num%i==0){
                num/=i;
                p.push_back(i);
            }
            if(num==1) break;
        }
    }
    if(num>1) p.push_back(num);
}
int n;
int f(int n,int m){
    return C[n+m-1][n-1];
}
void solve(){
    sort(p.begin(),p.end());

    int tot=0;
    int a[100];
    int sz=p.size();
    for(int i=0,j;i<sz;i=j)  {
        j=i;
        while(j<sz && p[j]==p[i])    {
            j++;
        }
        a[++tot]=j-i;
    }
    __int64 ans=1;
    for(int i=1;i<=tot;i++)     ans*=f(n,a[i]),ans%=mod;
    for(int i=1;i<=n;i++)
    {
        if(i&1)
        {
            __int64 tmp=1;
            tmp*=C[n][i]; tmp%=mod;
            for(int j=1;j<=tot;j++)
            {
                tmp*=f(n-i,a[j]);
                tmp%=mod;
            }
            ans-=tmp;
            ans=(ans%mod+mod)%mod;
        }
        else 
        {
            __int64 tmp=1;
            tmp*=C[n][i];tmp%=mod;
            for(int j=1;j<=tot;j++)
            {
                tmp*=f(n-i,a[j]);
                tmp%=mod;
            }
            ans+=tmp;
            ans=(ans%mod+mod)%mod;
        }
    }
    printf("%I64d
",ans);
}
int num[25];
int main()
{
    init();
    while(scanf("%d",&n)!=EOF)
    {
        p.clear();
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&num[i]);
            make(num[i]);
        }
        solve();
    }
    return 0;
}