状压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;
}