「HNOI 2006」花仙子的魔法

题目大意：求 $m$ 个 $n$ 维球体最多能把 $n$ 维空间划分成多少部分。$n \leq 15, m \leq 100$

打表找规律QAQ

设 $f[i][j]$ 表示 $i$ 维空间 $j$ 个球体，有

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

其中 $f[i][j-1]$ 表示前 $j-1$ 个球体划分到的空间数量，$f[i-1][j-1]$ 表示前 $j-1$ 个球体的切面把第 $j$ 个球体的切面划分成了多少部分。

#include <cstdio>
 
typedef long long LL;
LL f[20][105]; int n, m;
 
int main() {
    scanf("%d%d", &m, &n);
    f[1][0] = 1;
    for (int i = 1; i <= m; ++i) f[1][i] = i << 1;
    for (int i = 2; i <= n; ++i) {
        f[i][0] = 1;
        for (int j = 1; j <= m; ++j)
            f[i][j] = f[i-1][j-1] + f[i][j-1];
    }
    printf("%lld\n", f[n][m]);
    return 0;
}