BZOJ 2734 [HNOI2012] 集合選數 —— 矩陣分解 + 狀壓 DP 計數無相鄰選擇方案

BZOJ 2734：從 {1, 2, ..., n}（n ≤ 100000）選子集，約束：若選 x 則 2x 和 3x 不能選。求合法子集數模 1,000,000,001。

一、矩陣分解洞察

考慮以 2^a 3^b 形式的數。所有正整數可唯一分解為 k × 2^a 3^b，其中 k 不含因子 2、3（即 gcd(k,6)=1）。
對固定 k，所有形如 k·2^a·3^b ≤ n 的數構成一個二維網格：

k,   3k,   9k,   27k, ...
2k,  6k,  18k,  54k, ...
4k, 12k,  36k, 108k, ...
...

約束「選 x 禁 2x, 3x」在網格中轉化為：不能選相鄰格子（上下左右）。
不同 k 的網格互不干擾，總方案數 = 各網格方案數乘積。

二、網格狀壓 DP

網格行數 ≤ log₂ n ≤ 16，列數 ≤ log₃ n ≤ 10，實際最多 12 行。
逐行狀壓：f[row][mask] = 前 row 行，第 row 行選擇狀態為 mask 的方案數。
合法 mask：無相鄰 1（(mask & (mask<<1)) == 0）。
行間轉移：mask 與 prevMask 無垂直衝突（(mask & prevMask) == 0）。

三、關鍵代碼

ll calc(int x) { // 以 x 為左上角的網格方案數
    if (x > n) return 1;
    vector rows;
    for (int cur = x; cur <= n; cur *= 2) {
        int cnt = 0;
        for (int t = cur; t <= n; t *= 3) { ++cnt; vis[t] = true; }
        rows.push_back(cnt);
    }
    // DP
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int i = 0; i < rows.size(); ++i) {
        int cols = rows[i];
        for (int mask = 0; mask < (1<0) {
                if (mask & pmask) continue; // 行間相鄰
                f[i][mask] = (f[i][mask] + f[i-1][pmask]) % MOD;
            }
            if (i==0) f[i][mask] = 1;
        }
    }
    ll sum = 0;
    for (int mask = 0; mask < (1<

四、主流程
ll ans = 1;
for (int i = 1; i <= n; ++i)
    if (!vis[i] && i%2 && i%3) // i 不含因子 2、3
        ans = ans * calc(i) % MOD;
printf("%lld\n", ans);

五、複雜度

網格總數 ≈ n × (1-1/2) × (1-1/3) = n/3 ≈ 3.3×10⁴。
每網格行數 ≤ 12，列數 ≤ 10，狀態 2^10 = 1024，DP 極快。
總時間 < 0.5s，空間 < 10 MB。


六、關鍵點

數論分解：k × 2^a 3^b 唯一表示，將全局約束分解為獨立網格。
網格內約束轉化為「無相鄰選擇」，標準狀壓 DP 解決。
答案為各獨立網格方案數乘積（乘法原理）。