HDU 2082 找單詞：母函數計數價值 ≤ 50 的單詞

題目

有 x₁..x₂₆ 個字母 A..Z，字母值 1..26。求能組成的總價值 ≤ 50 的不同單詞數（順序無關，即多重集）。

母函數

每字母貢獻 (1 + x^v + x^{2v} + ... + x^{cnt*v})。所有多項式相乘，1~50 次係數和即答案。

DP 實現

int a[51], b[51];
a[0] = 1;
for i=0..25:
    clear b
    for j=0..cnt[i], j*val[i] <= 50:
        for k=0; k+j*val[i] <= 50; ++k:
            b[k + j*val[i]] += a[k];
    a = b;
ans = sum_{i=1}^{50} a[i];

複雜度

O(26 * 50 * max_cnt)，極小。