BZOJ 2734 [HNOI2012] 集合選數：狀壓 DP + 矩陣分組 (互質分解 + 乘法原理)

問題

集合 S={1,2,...,n}。選子集，要求任意兩數 x,y 滿足 x≠2y 且 x≠3y。求合法子集數模 1e9+1。

核心洞察：按「與 6 互質」分組建矩陣

對每個與 6 互質的數 x (即 x%2≠0 且 x%3≠0)，構建無限矩陣：
第 0 行：x, 3x, 9x, 27x... (×3)
第 1 行：2x, 6x, 18x...
第 2 行：4x, 12x, 36x...
... (×2 向下)
矩陣內相鄰格子 (上下/左右) 滿足 2倍/3倍關係，**不能同時選**。不同 x 的矩陣互不干擾 (因任何數唯一分解為 x·2^a·3^b)。

子問題：單矩陣合法選法計數

矩陣有限 (≤n)。對每行做狀壓 DP：狀態表示該行選哪些列，要求行內無相鄰選 (左右相鄰即 ×3 關係)，且與上一行無同列同時選 (上下相鄰即 ×2 關係)。行數 ≤ log₂n ≤ 10，列數 ≤ log₃n ≤ 7，狀態數極小。

DP 遞推

int solve(int x) { // x 為矩陣基數 (與 6 互質)
    vector rows;
    for (int i=0; x*(1<

總答案 = 所有矩陣方案數乘積 (模 MOD)
利用乘法原理，不同 x 矩陣獨立，總方案數 = ∏ solve(x)。

代碼精華 (官方題解風格)
const int MOD = 1000000001;
bool ok[1<<12]; // 狀態合法：無相鄰 1
int f[2][1<<12];

int dp(int x) {
    int rows=0, cols[12];
    for (int i=0; x*(1<>n;
    for (int i=0;i<1<<12;i++) ok[i]=!(i&(i<<1)) && !(i&(i>>1));
    long long ans=1;
    for (int x=1;x<=n;x++) if (x%2 && x%3) ans=ans*dp(x)%MOD;
    cout<

複雜度
x 取值 ~ n/3，每個 dp 狀態數 < 2^12，總操作 ~ 10^7，1 秒內輕鬆過。