Codeforces 893E Counting Arrays：dp + 线性筛 + 分解质因数 + 组合数结论

题目链接：http://codeforces.com/problemset/problem/893/E

题意：

　　共q组数据(q <= 10^5)，每组数据给定x,y(x,y <= 10^6)。

　　问你有多少种长度为y，乘积为x的整数数列。（可以有负数）

题解：

　　首先考虑数列只有正整数的情况。

　　将x分解质因数：x = ∑ a[i]*p[i]

　　由于x较大，所以要先用线性筛求出素数，再枚举素数分解质因数。

　　那么一个乘积为x的数列可以看做，将x的所有∑ p[i]个质因子，分配到了y个位置上。

　　设f(i)表示：将p[i]个质因子a[i]，分配到y个位置上的方案数。

　　所以乘积为x的数列总数ans = ∏ f(i)。

　　其中，f(i)等价于：长度为y，和为p[i]的数列总数。

　　由于是多组数据，所以要预处理出对于所有长度的f(i)。

　　dp[i][j]表示y = i时，之和为j的数列总数。

　　转移：dp[i][j] = ∑ dp[i-1][0 to j]

　　用前缀和优化转移，总复杂度O(nlogn)。

　　这样就求出了只考虑正整数情况下的数列总数：ans = ∑ dp[y][p[i]]

　　然后考虑加负号的情况。

　　由于x为正数，所以只能加偶数个负号。

　　所以加负号的方案数 = C(y,0) + C(y,2) + C(y,4) + ... + C(y,偶数)

　　有一个组合数结论：∑ C(n,偶数) = ∑ C(n,奇数) = 2^(n-1)。

　　所以最终ans = ans * (2^(y-1))即为最终答案。

AC Code:

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #define MAX_X 1000005
 5 #define MAX_P 25
 6 #define SET_X 1000000
 7 #define SET_P 20
 8 #define MOD 1000000007
 9 
10 using namespace std;
11 
12 int x,y,q;
13 int cnt,tot=0;
14 int p[MAX_P];
15 int pw[MAX_X];
16 int prime[MAX_X];
17 int dp[MAX_X][MAX_P];
18 int sum[MAX_X][MAX_P];
19 bool mark[MAX_X];
20 
21 void cal_dp()
22 {
23     memset(dp,0,sizeof(dp));
24     memset(sum,0,sizeof(sum));
25     dp[0][0]=1;
26     for(int i=0;i<=SET_P;i++) sum[0][i]=1;
27     for(int i=1;i<=SET_X;i++)
28     {
29         for(int j=0;j<=SET_P;j++)
30         {
31             dp[i][j]=sum[i-1][j];
32             sum[i][j]=(sum[i][j-1]+dp[i][j])%MOD;
33         }
34     }
35 }
36 
37 void cal_pw()
38 {
39     pw[0]=1;
40     for(int i=1;i<=SET_X;i++) pw[i]=(pw[i-1]<<1)%MOD;
41 }
42 
43 void sieve()
44 {
45     memset(mark,false,sizeof(mark));
46     for(int i=2;i<=SET_X;i++)
47     {
48         if(!mark[i]) prime[++tot]=i;
49         for(int j=1;j<=tot && (long long)i*prime[j]<=SET_X;j++)
50         {
51             mark[i*prime[j]]=true;
52             if(!(i%prime[j])) break;
53         }
54     }
55 }
56 
57 void resolve()
58 {
59     int t=x;
60     cnt=0;
61     memset(p,0,sizeof(p));
62     for(int i=1;i<=tot && prime[i]*prime[i]<=x;i++)
63     {
64         if(t%prime[i]==0)
65         {
66             cnt++;
67             while(t%prime[i]==0)
68             {
69                 t/=prime[i];
70                 p[cnt]++;
71             }
72         }
73     }
74     if(t!=1) p[++cnt]=1;
75 }
76 
77 int cal_ans()
78 {
79     resolve();
80     long long ans=1;
81     for(int i=1;i<=cnt;i++) ans=ans*dp[y][p[i]]%MOD;
82     return ans*pw[y-1]%MOD;
83 }
84 
85 int main()
86 {
87     sieve();
88     cal_dp();
89     cal_pw();
90     cin>>q;
91     while(q--)
92     {
93         cin>>x>>y;
94         cout<<cal_ans()<<endl;
95     }
96 }