题目地址:http://poj.org/problem?id=3181

题目大意

大意是,给你$N$元钱,和价值$1-m$元的$m$个物品无限个,求出恰好组成$n$元的方案数。

思路(母函数)

这题可以用母函数搞,注意高精度。$$G(x) = (1+x+x^2+\cdots+x^m)(1+x^2+x^4+\cdots+x^m)(1+x^3+x^6+\cdots+x^m)\cdots (1+x^m)$$

展开后$x^N$的系数即为答案。

AC代码(母函数)

using namespace std;
const int MAX_N = 1005;
int N, K;
struct BigInt {
    const static int nlen = 4;    // 控制每个数组数字长度,默认为4,计算乘法的时候每个数组相乘也不会溢出int范
    const static int mod = 10000;    // 值为10^nlen
    short n[10], len;            // 最多存4*1000位长度,可调,short占的内存小,但是速度慢
     BigInt() {
        memset(n, 0, sizeof(n));
        len = 1;
    } BigInt(int num) {
        len = 0;
        while (num > 0) {
            n[len++] = num % mod;
            num /= mod;
        }
    }
    BigInt(const char *s) {
        int l = strlen(s);
        len = l % nlen == 0 ? l / nlen : l / nlen + 1;
        int index = 0;
        for (int i = l - 1; i >= 0; i -= nlen) {
            int tmp = 0;
            int j = i - nlen + 1;
            if (j < 0)
                j = 0;
            for (int k = j; k <= i; ++k)
                tmp = tmp * 10 + s[k] - '0';
            n[index++] = tmp;
        }
    }
    BigInt operator+(const BigInt & b) const {    // 加法
        BigInt res;
         res.len = max(len, b.len);
        for (int i = 0; i < res.len; ++i) {
            res.n[i] += (i < len ? n[i] : 0) + (i < b.len ? b.n[i] : 0);
            res.n[i + 1] += res.n[i] / mod;
            res.n[i] = res.n[i] % mod;
        } if (res.n[res.len] > 0)
            ++res.len;
        return res;
    }
    BigInt operator*(const BigInt & b) const {    // 乘法
        BigInt res;
        for (int i = 0; i < len; ++i) {    // 类似母函数,第一个数组
            int up = 0;            // 进位
            for (int j = 0; j < b.len; ++j) {    // 第二个数组
                int tmp = n[i] * b.n[j] + up + res.n[i + j];    // 控制nlen=4是防止tmp溢出
                 res.n[i + j] = tmp % mod;
                 up = tmp / mod;
            } if (up != 0)
                 res.n[i + b.len] = up;
        }
        res.len = len + b.len;
        while (res.n[res.len - 1] == 0 && res.len > 1)
            --res.len;
        return res;
    }
    void show() const {
        printf("%d", n[len - 1]);    // 先输出最高位,后面可能需要前导0
        for (int i = len - 2; i >= 0; --i)
            printf("%04d", n[i]);    // 前导0,%04d和nlen一致
        printf("\n");
}};


BigInt c1[MAX_N], c2[MAX_N];

void solve()
{
    for (int i = 0; i <= N; ++i) { // 母函数核心部分
        c1[i] = 1;
        c2[i] = 0;
    }
    for (int i = 2; i <= K; ++i) {
        for (int j = 0; j <= N; ++j) {
            for (int k = 0; k + j <= N; k += i) {
                c2[k + j] = c2[k+j] + c1[j];
            }
        }
        for (int j = 0; j <= N; ++j) {
            c1[j] = c2[j];
            c2[j] = 0;
        }
    } // 母函数结尾
    c1[N].show();
}

int main()
{
#ifdef Oj
    freopen("3181.in", "r", stdin);
#endif
    cin >> N >> K;
    solve();
    return 0;
}

思路(DP)

这题还是比较简单的,相对于各个物品有限个来说。算是多重部分和问题。

定义$dp[i+1][j]$为用前$i$个数字凑成$j$的方案数,那么有$dp[i+1][j] = \sum_{k=0}^{k i\leq j} dp[i][j-ki]$。

得出AC代码:

AC代码(DP)

using namespace std;

const int MAX_N = 1005;
const int MAX_K = 105;
int N, K;
long long int dp[MAX_K][MAX_N][2]; // 前K个数组成n的个数
const long long Mod = 100000000000000000; // 大数处理

void solve() {
    dp[0][0][1] = 1; // 前0个数凑成0的方案数为1
    for(int i=1; i<=K; ++i) {
        for(int j=0; j<=N; ++j) {
            for(int k=0; k*i <= j; ++k) {
                dp[i][j][0] += dp[i-1][j-k*i][0];
                dp[i][j][1] += dp[i-1][j-k*i][1];
                dp[i][j][0] += dp[i][j][1]/Mod;
                dp[i][j][1] %= Mod;
            }
        }
    }
    if(dp[K][N][0]) cout << dp[K][N][0];
    cout << dp[K][N][1] << endl;
}

int main()
{
#ifdef Oj
    freopen("3181.in", "r", stdin);
#endif
    cin >> N >> K;
    solve();
    return 0;
}

继续优化,由$dp[i+1][j] = \sum_{k=0}^{k i\leq j} dp[i][j-ki]$展开得

$$dp[i+1][j] = \sum_{k=0}^{k i\leq j} dp[i][j-ki] = dp[i][j]+dp[i][j-i]+dp[j-2i]+\cdots+dp[i][j-ki]$$

由于第二维每次减一个$i$,不仿展开

$$dp[i+1][j-i] = \sum_{k=0}^{k i\leq j} dp[i][j-i-ki] = dp[i][j-i]+dp[j-2i]+\cdots+dp[i][j-ki]$$

对比$dp[i+1][j]$的展开式,发现$dp[i+1][j-i]$少了一项$dp[i][j]$,于是得出递推关系

$$dp[i+1][j] = dp[i+1][j-i] + dp[i][j]$$

这样就可以化三阶为二阶了。

using namespace std;

const int MAX_N = 1005;
const int MAX_K = 105;
int N, K;
long long int dp[MAX_K][MAX_N][2]; // 前K个数组成n的个数
const long long Mod = 100000000000000000;

void solve() {
    dp[0][0][1] = 1;
    for(int i=1; i<=K; ++i) {
        for(int j=0; j<=N; ++j) {
            if(j >= i) {
                dp[i][j][1] = dp[i-1][j][1] + dp[i][j-i][1];
                dp[i][j][0] = dp[i-1][j][0] + dp[i][j-i][0];
                dp[i][j][0] += dp[i][j][1] / Mod;
                dp[i][j][1] %= Mod;
            }
            else {
                dp[i][j][1] = dp[i-1][j][1];
                dp[i][j][0] = dp[i-1][j][0];
            }
        }
    }
    if(dp[K][N][0]) cout << dp[K][N][0];
    cout << dp[K][N][1] << endl;
}

int main()
{
#ifdef Oj
    freopen("3181.in", "r", stdin);
#endif
    cin >> N >> K;
    solve();
    return 0;
}