BZOJ 1197 [HNOI2006]花仙子的魔法 (数学题)

题面：洛谷传送门 BZOJ传送门

非常有意思的一道数学题，浓浓的$CF$风，然而我并没有想出来..

我们想把一个$n$维空间用$n$维球分成尽可能多的块

而新增加一个$n$维球时，肯定要尽可能多地切割前几个球围成的不同空间

画画图容易发现$n=1$的规律，因为一条线段只能在两个端点处切割这条直线，所以$f(n)=2n$

$n=2$的规律不太好找，但突破口也在这了..

发现当一个新的圆加入到图里时，新圆会切割原来的圆，把原图分成了更多的小块

我们把新圆的圆周看成一条线段，把旧圆和新圆的两个交点形成的弧看成一条线段

诶？问题似乎变成了一维的，事实上我们是再用一个新的直线去切原来的直线

原来直线数目是$(i-1)$，因此$f[i]=f[i-1]+2(i-1)$

那如果把这个问题推广到更高的维度呢？

结论还是成立的，我们在i维空间内，用一个$i$维球去切$j-1$个$i$维球

新产生的块数目就是用$i-1$维球去切$j-1$个$i-1$维球

因此得到递推式$f[i,j]=f[i-1,j-1]+f[i,j-1]$

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N1 105

 #define ll long long

 #define ull unsigned long long

 #define dd double

 #define inf 0x3f3f3f3f

 using namespace std;

 int gint()

 {

     int ret=,fh=;char c=getchar();

     while(c<''||c>''){if(c=='-')fh=-;c=getchar();}

     while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}

     return ret*fh;

 }

 ull f[N1][N1];

 int n,m;

 int main()

 {

     scanf("%d%d",&m,&n); int i,j;

     for(i=;i<=n+;i++)

         for(j=,f[i][]=;j<=m;j++)

             f[i][j]=f[i-][j-]+f[i][j-];

     printf("%llu\n",f[n+][m]);

     return ;

 }