这是蓝题？？？

题目链接：UVA10253 Series-Parallel Networks

题意：

现有 $n$ 条电线，现可以对他们进行串联或并联。串联与并联的顺序都是无关紧要的，且所有电线必须成为一个联通块。问 $n$ 条电线的形态有多少种

$n\le 30$

$\texttt{Solution}$

具体哪些属于一种情况可以去原题面看。

明显的计数题，但对这样一个模型进行 $\texttt{dp}$ 是很难的 反正我不会，因此考虑转化。

我们可以发现，每一个电线形态都可以表示为若干个串联、并联的嵌套。首先可以将某一个状态拆分成若干电线形态串联（并联），然后对于每一个拆分出来的电线形态，他们要么是单独的一根电线，要么是若干电线形态的并联（串联）。因为如果仍然是串联（并联）的话，在上一步我们就会认为他们是两个不同的电线形态。

不难发现这个过程是可以一直进行下去，直到所有的电线形态都被分解为若干单独电线的串联、并联。

这类似一个树形结构，对于一个电线形态，首先以当前形态的串并联状态建立一个节点，然后将所有这个状态的组成部分当做其儿子，一直进行重复，直到某个节点仅代表单根电线为止。

不难发现每一棵这样的树唯一确定一种电线状态，且很快可以发现这样一棵树的性质：

1.对于任意非叶子节点，该节点所代表的串并联状态一定是与其父亲不同的。也就是说，非叶子节点的串并联状态在任意一条从根开始的链上，交替出现。

2.任意非叶子节点，其儿子个数一定不少于 $2$ 个。

3.叶子节点总数为 $n$。

从性质 $\texttt{1}$ 可以发现，只要根的串并联状态确定下来，整棵树每个非叶子节点的串并联状态就都确定下来了。因此如果这样的树的个数为 $x$，则最终答案应该为 $x \times 2$。

因此现在我们的问题转化为：

给定 $n$，求有多少树满足：任意非叶子节点的儿子不少于 $2$，叶子节点个数为 $n$。

这可以用 $\texttt{dp}$ 来解决。

设 $dp[x][s]$ 为共有 $s$ 个叶子，且根节点的每一棵子树中，包含叶子最多的那棵所包含的叶子个数不超过 $x$。

设 $f[s]$ 为共有 $s$ 个叶子的满足条件的树的个数。

有 $f[s] = dp[s-1][s]$。

那么有转移：

$$dp[x][s] = \sum_{p=0} dp[x-1][s-x\times p] \times \binom{f[x]+p-1}{p},(x\times p \le s)$$

可以理解为枚举具有 $x$ 个叶子的儿子有多少个，剩下的儿子包含的叶子个数应该小于等于 $x-1$。现在我们需要向 $dp[x-1][s-x\times p]$ 所代表的那棵树中插入 $p$ 个包含 $x$ 个叶子的树作为根节点的儿子。我们并不关心选择的这 $p$ 棵树顺序如何，只关心每一种树选择了多少。

因此我们只需要得到从 $f[x]$ 种树中选择 $p$ 棵的方案数即可。令 $v_i$ 为第 $i$ 种选了 $v_i$ 个的话，有方程：

$$\sum_{i=1}^{f[x]} v_i=n,(\forall v_i \ge 0)$$

这是经典的组合问题，我们可以使用隔板法的方法。但隔板法不能处理 $0$，那么我们就多插入一些点即可。方案数为：

$$\binom{f[x]+p-1}{p}$$

因为数据很小，所以组合数暴力算，暴力算出每个 $\texttt{dp}$ 和 $\texttt{f}$，然后多组询问 $O(1)$ 回答。

$\texttt{Code}:$

//Code By CXY07
#include<bits/stdc++.h>
using namespace std;

//#define FILE
#define int long long
//#define LL long long
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fst first
#define scd second
#define inv(x) ksm(x,mod - 2)
#define lowbit(x) (x & (-x))

const int MAXN = 110;
const int INF = 2e9;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;

int n;
int dp[MAXN][MAXN],ans[MAXN];

template<typename T> inline void read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
    a *= f;
}

int C(int x,int y) {
    int res = 1;
    for(int i = x;i >= x - y + 1; --i) res *= i;
    for(int i = 1;i <= y; ++i) res /= i;
    return res;
}

signed main () {
#ifdef FILE
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    for(int i = 0;i < 100; ++i) dp[i][0] = dp[i][1] = dp[1][i] = 1;
    ans[1] = 1;
    for(int i = 2;i < 100; ++i) {
        ans[i] = dp[i - 1][i];
        for(int j = 2;j < 100; ++j) {
            for(int p = 0;p * i <= j; ++p) 
                dp[i][j] += C(ans[i] + p - 1,p) * dp[i - 1][j - p * i];
        }
    }
    while(1) {
        read(n);
        if(!n) return 0;
        printf("%lld\n",(n == 1) ? 1 : (ans[n] << 1));
    }
    return 0;
}

我觉着，这怎么着也要评个紫吧 $\texttt{ovo}$。也可能是我太菜了