状压DP
状压 \(DP\) 是一种基于二进制数的 \(DP\)。
T1
题目大意
将一个整数 \(N\) 分解成若干个小整数的乘积，满足：
分解出的整数必须来自集合 \(S\)。
分解出的整数必须互不相同，且两两互质。
求有多少种分解方法。
算法分析
将 \(N\) 进行质数分解，然后将集合中的每一个数 \(a_i\) 也进行质数分解。
可以发现，每个 \(a_i\) 要么分解出来的质因子的指数等于 \(N\) 对应的质因子的指数，要么指数就为 \(0\)。
粗略的讲就是一次性将质因子提供完，要么就不提供。
于是我们就可以对于每一个质因子分配一个 \(01\) 标记，表示这个质因子是否能够全部提供。
剩下的就是状压 \(dp\) 了。
时空复杂度分析
时间：\(O(N\sqrt N)\)
空间：\(O(m)\)
代码
#include<iostream>
#include<cmath>
#include<map>
#define int long long
using namespace std;
inline int read(){register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}
inline void write(int x){if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');}
const int N = 505, MAXN = 1e4;
int k, n;
int p[N][20], q[N][20], s[N], prime[MAXN], pn[20], Q[20], cnt, tot, dp[1 << 20];
map<int, int> v;
signed main(){
k = read(), n = read();
for (int i = 1; i <= n; i++){
int x = read();
for (int j = 2; j <= sqrt(x); j++){
if (x % j) continue;
p[i][++s[i]] = j, prime[++cnt] = j;
while (x % j == 0){
x /= j;
q[i][s[i]]++;
}
}
if (x > 1) p[i][++s[i]] = x, q[i][s[i]]++, prime[++cnt] = x;
}
for (int i = 1; i <= cnt; i++){
if (k % prime[i] == 0 && !v[prime[i]]){
pn[++tot] = prime[i], v[pn[tot]] = tot;
while (k % prime[i] == 0){
k /= prime[i];
Q[tot]++;
}
}
}
if (k > 1){
cout << 0;
return 0;
}
dp[0] = 1;
for (int i = 1; i <= n; i++){
int x = 0;
for (int j = 1; j <= s[i]; j++){
if (v[p[i][j]] && Q[v[p[i][j]]] == q[i][j]){
x |= 1 << (v[p[i][j]] - 1);
}else{
x = -1;
break;
}
}
if (x != -1){
for (int j = (1 << tot) - 1; j >= 0; j--){
if (!(j & x)) dp[j | x] += dp[j];
}
}
}
cout << dp[(1 << tot) - 1];
return 0;
}
