「UVa 10253」Series-Parallel Networks - 整数划分 + 组合数

串并联网络有两个端点，一个是源，一个是汇，递归定义如下：

一条单独的边是串并联网络；
若和是串并联网络，则将它们的源和汇分别接在一起也能得到串并联网络（并联）；
若和是串并联网络，则将的源和的汇接在一起也能得到串并联网络（串联）；

并联或串联在一起的各个部分可以调换顺序，顺序改变后的串并联网络和之前是相同的。求条边能组成多少种不同的串并联网络。

链接

题解

书上的解法，考虑每个串并联网络都是一棵树，组成网络的几个部分是树的子节点，那么叶子节点就对应了网络中的边，并且整棵树从根到叶子，父子关系所代表的连接方式是交替着的，某一层是并联，则下一层即为串联。同一种树的形态，第一层的连接方式不同，也就对应了两个网络。

问题转化为，求有多少子节点有序且有个叶子节点的形态不同的树。设为答案，则可以根据各个子树所『分得』的叶子节点数量来递归求解 —— 回溯法枚举的整数划分，就得到了单层子树所有的情况。

假设整数划分的某一种方案中，有个，求这棵子树的方案数可使用组合数：从个中选择个，可重复选择，答案为。计算出每一组子树的方案数，相乘即为根节点的答案。

最终答案为，注意时答案为。

代码

#include <cstdio>
#include <vector>

const int MAXN = 30;

long long solve(int n);
void search(std::vector<int> &v, int t, int r);

long long C(long long n, long long m) {
    long long result = 1;
    for (int k = 1; k <= m; k++) {
        result = result * (n - k + 1) / k;
    }
    return result;
}

long long process(std::vector<int> &v) {
    long long ans = 1;
    int count = 0, last = 0;
    for (int i = 0; i < (int)v.size(); i++) {
        if (last != v[i] && last != 0) {
            ans *= C(solve(last) + count - 1, count);
            count = 1;
        } else {
            count++;
        }

        last = v[i];
    }

    ans *= C(solve(last) + count - 1, count);

    // printf("process = %lld\n", ans);
    return ans;
}

long long divide(std::vector<int> &v, int r, int t = 1) {
    if (r == 0) {
        if (v.size() == 1) return 0;
        // for (std::vector<int>::const_iterator p = v.begin(); p != v.end(); p++) printf("%d ", *p);
        // putchar('\n');
        // return 0;
        return process(v);
    }

    long long ans = 0;
    for (int i = t; i <= r; i++) {
        v.push_back(i);
        ans += divide(v, r - i, i);
        v.pop_back();
    }

    return ans;
}

long long solve(int n) {
    static long long mem[MAXN];
    static bool calced[MAXN];
    long long &ans = mem[n - 1];

    if (calced[n - 1]) return ans;
    calced[n - 1] = true;

    if (n == 1) return ans = 1;

    std::vector<int> v;
    ans = divide(v, n);

    // printf("f(%d) = %lld\n", n, ans);
    return ans;
}

int main() {
    for (int n; ~scanf("%d", &n) && n != 0; printf("%lld\n", n == 1 ? 1 : solve(n) * 2));
    return 0;
}