题解 P4176 【[HNOI2006]花仙子的魔法】

· · 题解

看到这道题，首先想到的是打个表找规律，于是

n\m:0   1   2   3   4   5   6
1:  1   2   4   6   8   10  12
2:  1   2   4   8   14  22  32
3:  1   2   4   8   16  30  52

(打三维的表时差点猝死)

于是我们发现a[n][m]=a[n][m-1]+a[n-1][m-1]。

AC代码：

#include<bits/stdc++.h>
using namespace std;
unsigned long long a[101][17],m,n;
int main()
{
    a[0][1]=1;                          //初始化
    for(int i=1;i<101;i++)a[i][1]=i<<1;             //初始化
    for(int i=2;i<16;i++)
    {
        a[0][i]=1;                      //初始化
        for(int j=1;j<101;j++)a[j][i]=a[j-1][i]+a[j-1][i-1];    //重点
    }
    scanf("%lld%lld",&m,&n);
    printf("%lld",a[m][n]);
    return 0;
}
//由于a[101][17]要比a[17][101]快，所以我写程序时把m和n反过来了

但是打表的结论不一定准确，所以还要考虑一下结论的正确性。

首先，显然后加入的图形应与原来的全部图形相交，下面是分析：（设n维空间，m个图形的情况答案为a[n][m]）

先从一维开始，一维中距离一个点一定距离的点构成的图形就是2个点，m个图形就有2m个点，就有2m段（由题意，最左边和最右边的两区域应视为一个）。

二维就是圆分平面，第m个圆与前m-1个圆相交，它就被2m-2个交点分成了2m-2（a[1][m-1]）条曲线，每条线把原来的一个区域分成了2个，答案就增加了2m-2（a[1][m-1]），所以a[2][m]=a[2][m-1]+a[1][m-1]。

三维是球分空间，还是考虑第m个球的情况，它与前m-1个球相交，两球相交的公共部分是一个圆，于是这个球就被m-1个圆分成了a[2][m-1]个区域，每个区域都会把原来的一个空间分成2个，答案就要增加了a[2][m-1]，所以a[3][m]=a[3][m-1]+a[2][m-1]。

接着就可以考虑n维空间了，第m个东西和前m-1个东西相交，就被分成了a[n-1][m-1]个n-1维的东西，每个n-1维的东西都把原来的一个n维的东西分成两个，答案就增加a[n-1][m-1],所以a[n][m]=a[n][m]+a[n-1][m-1]。

再初始化1维（a[1][m]=2m）和没有分的情况(a[n][0]=1)就可以了。