HDU 4390 Number Sequence [容斥原理]

　　求把一个数拆成N个非1的数相乘的方案数有多少种（顺序不一样的算不一样的）。

　　如果不考虑是否为1的方案数，对原数所有的质因数直接用插板法然后乘起来就可以了，麻烦的是有一个所有数都不能为1的问题，这里可以用容斥原理组成。用f(i)表示有i~N个1的方案数,用x[i]表示确切有i个0的方案数。我们可以得到如下方程组：

f(0)=1x[0]+1x[1]+1x[2]+1x[3]+....;

f(1)= 1x[1]+2x[2]+3x[3]+....;

f(2)= 1x[1]+3x[3]+...;

f(3)= 1x[3]+...;

　　比如在算f(1)的时候，假设有3位数，我们枚举每一位为1，会产生重复的情况，这个稍微推一下就知道了。

　　所以最后的x[0]=f(0)-f(1)+f(2)-f(3)....

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 #define MAXN 1000005
 5 #define MAXC 110
 6 #define MOD 1000000007
 7 typedef long long LL;
 8 int n,b[22],maxs;
 9 int cc[MAXC][MAXC];
10 int tot[MAXN],pri[MAXN],pris;
11 void init(){
12     memset(pri,0,sizeof pri),pri[1]=1;
13     for(int i=1;i<MAXN;i++){
14         if(pri[i])continue;
15         for(int j=i*2;j<MAXN;j+=i)pri[j]=1;
16     }
17     pris=0;
18     for(int i=2;i<MAXN;i++)
19         if(!pri[i])pri[pris++]=i;
20     for(int i=0;i<MAXC;cc[i++][0]=1)
21         for(int j=1;j<=i;j++)
22             cc[i][j]=((LL)cc[i-1][j-1]+cc[i-1][j])%MOD;
23 }
24 int main(){
25     //freopen("test.in","r",stdin);
26     init();
27     while(scanf("%d",&n)!=EOF){
28         memset(tot,0,sizeof tot),maxs=0;
29         for(int i=1;i<=n;i++){
30             scanf("%d",&b[i]);
31             for(int j=0;j<pris&&pri[j]<=b[i];j++){
32                 while(b[i]%pri[j]==0){
33                     tot[j]++,b[i]/=pri[j];
34                     maxs=std::max(maxs,j+1);
35                 }
36             }
37         }
38         LL ans=0,tmp;
39         //容斥原理
40         for(int i=0;i<n;i++){
41             tmp=cc[n][i];
42             for(int j=0;j<maxs;j++)
43                 tmp=tmp*cc[n-i-1+tot[j]][n-i-1]%MOD;
44             ans+=(i&1)?-tmp:tmp;
45             ans%=MOD;
46         }
47         printf("%I64d\n",(ans%MOD+MOD)%MOD);
48     }
49     return 0;
50 }