ACdream 1431 Sum vs Product：DFS 枚舉非 1 數字組合計算 Beautiful 集合數

ACdream 1431：數字集合乘積等於和的方案數

找 n 個正整數，乘積 = 和。觀察：解的形式必為大量 1 + 少數 >1 的數。如 n=5：{1,1,1,2,5}, {1,1,1,3,3}, {1,1,2,2,2}。設非 1 數字為 a₁..aₖ (k≤n)，乘積 P，和 S，需補 (P-S) 個 1，總數 k+(P-S)=n ⇒ P-S+k=n。DFS 枚舉非 1 組合（非遞減避免重複），記錄有效 n。

DFS 邏輯

int ans[505];
void dfs(int cnt, int prod, int sum, int last) { // cnt: 非1個數
    for(int x=last; x<=500; x++){
        int nprod=prod*x, nsum=sum+x, ncnt=cnt+1;
        int n = ncnt + nprod - nsum; // 總數 = 非1數 + 補1數
        if(n>500) break;
        ans[n]++;
        dfs(ncnt, nprod, nsum, x);
    }
}
int main(){
    dfs(0,1,0,2);
    // 輸出 ans[n]
    return 0;
}

關鍵優化

• 非 1 數字按非遞減序枚舉，避免排列重複。
• 乘積增長極快，`nprod > 1000` 即可剪枝（n≤500）。
• 預計算 ans[2..500]，查詢 O(1)。

結果驗證

n=2 → 1 ({2,2})；n=5 → 3（樣例吻合）。