「Bzoj 4197」「NOI2015」寿司晚宴 (状压DP + 质因数分解)

BZOJ 4197
题意:给定$n$,求出选择两个不相交集合$A,B$,不存在$d$使得$d|(x\in A), d|(y\in B)$的方案。

我们发现$n=500$以内质数小于$\sqrt n$的只有$8$个,我们考虑状压小质数当做背包容量,然后再用大质数(每个数只有最多一个)来分组做分组背包。

设$dp(S,T)$为选的集合分别是$S,T$的方案

每次大质数相同的一起转移,考虑转移时设$f(S,T,0/1)$表示大质数放$S$还是$T$的方案。

然后分别转移即可,$dp(S,T)=f(S,T,0)+f(S,T,1)-dp(S, T)$

没有大质数的可以处理完马上转移,具体看代码实现,比较简单

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    LL MO, dp[260][260], f[2][260][260];
    int n;
    int pri[10] = {2, 3, 5, 7, 11, 13, 17, 19};

    struct data {int st, pri;} a[505];
    bool cmp(data a, data b) {return a.pri < b.pri;}

    void clean() {
    }
    int solve() {

        clean();
        cin >> n >> MO;
        for (int i = 1; i < n; ++i) {
            int tmp = i + 1;
            for (int j = 2; j * j <= tmp; ++j) {
                if (tmp % j == 0) {
                    for (int k = 0; k < 8; ++k) if (j == pri[k]) a[i].st |= (1 << k);
                    while (tmp % j == 0) tmp /= j;
                }
            }
            if (tmp != 1) {
                if (tmp > 19) a[i].pri = tmp;
                else {
                    for (int k = 0; k < 8; ++k) if (tmp == pri[k]) a[i].st |= (1 << k);
                }
            }
        }
        sort(a + 1, a + n, cmp);
        dp[0][0] = 1;
        for (int i = 1; i < n; ++i) {
            if (i == 1 || a[i].pri != a[i - 1].pri || a[i].pri == 0) memcpy(f[0], dp, sizeof dp), memcpy(f[1], dp, sizeof dp);
            for (int S1 = 255; ~S1; --S1) {
                for (int S2 = 255; ~S2; --S2) {
                    if (S1 & S2) continue ;
                    if (!(a[i].st & S2)) (f[0][S1 | a[i].st][S2] += f[0][S1][S2]) %= MO;
                    if (!(a[i].st & S1)) (f[1][S1][S2 | a[i].st] += f[1][S1][S2]) %= MO;    
                }
            }
            if (i == n - 1 || a[i].pri != a[i + 1].pri || a[i].pri == 0) {
                for (int S1 = 255; ~S1; --S1) {
                    for (int S2 = 255; ~S2; --S2) {
                        if (S1 & S2) continue ;
                        dp[S1][S2] = ((f[0][S1][S2] + f[1][S1][S2] - dp[S1][S2]) % MO + MO) % MO;
                    }
                }
            }
        }
        LL ans = 0;

        for (int S1 = 0; S1 <= 255; ++S1) {
            for (int S2 = 0; S2 <= 255; ++S2) {
                if (S1 & S2) continue ;
                (ans += dp[S1][S2]) %= MO;
            }
        }
        cout << ans;

        return 0;
    }  
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------