33OJ
登录 注册

#P4176. [HNOI2006] 花仙子的魔法

[HNOI2006] 花仙子的魔法

题目描述

相传,在天地初成的远古时代,世界上只有一种叫做“元”的花。接下来,出现了一位拥有魔法的花仙子,她能给花附加属性,从此,“元”便不断变异,产生了大千世界千奇百怪的各种各样的花。据说,花仙子既可存在于二维空间(平面),又可存在于三维空间(立体),还可存在于 nn 维空间(想象)。二维空间的点可用向量 (x1,x2)(x_1,x_2) 表示,三维空间的点可用向量 (x1,x2,x3)(x_1,x_2,x_3) 表示,一般来说,nn 维空间的点可用向量 (x1,x2,⋯ ,xn)(x_1,x_2,\cdots,x_n) 表示。而 nn 维空间中两点 (x1,x2,⋯ ,xn)(x_1,x_2,\cdots,x_n) 与 (w1,w2,⋯ ,wn)(w_1,w_2,\cdots,w_n) 之间的距离定义为

∑i=1n(xi−wi)2.\sqrt{\sum_{i=1}^{n}(x_i-w_i)^2}.

在 nn 维空间中,花仙子每实施魔法就要选择一个参考点 (w1,w2,⋯ ,wn)(w_1,w_2,\cdots,w_n) 和一个作用半径 rr,并且参考点的位置和作用半径的大小可以任意选择。这时,nn 维空间中所有与参考点 (w1,w2,⋯ ,wn)(w_1,w_2,\cdots,w_n) 之间的距离小于作用半径 rr 的花都会受到这次魔法的影响。每次魔法都会给受到影响的花带来不同的属性,且效果可以叠加。一般来说,若花仙子总共实施了 mm 次魔法,则 nn 维空间中处于某点的花所具有的属性可用长度为 mm 的二进制串 (a1,a2,⋯ ,am)(a_1,a_2,\cdots,a_m) 来描述,其中对 1≤i≤m1\le i\le m,若该花受到第 ii 次魔法的影响,则 aia_i 的值为 11,否则为 00。显然,不同的属性对应不同的花。

现在的问题是:花仙子在 nn 维空间中实施了 mm 次魔法后,最多能得到多少种不同的花?

输入格式

包含两个整数,并用一个空格隔开,第一个整数表示实施魔法的次数 mm,第二个整数表示空间的维数 nn。其中,1≤m≤1001\le m\le 100,1≤n≤151\le n\le 15。

输出格式

输出一行一个整数表示答案。

3 1
6

提示

样例解释:

m=3, n=1m=3,\ n=1。一维空间中每次魔法是一个开区间。取三个开区间如 (0,5),(2,7),(4,9)(0,5),(2,7),(4,9),端点交错。

它们将数轴分成若干段,对应二进制串:

000, 100, 110, 111, 011, 001, 000000,\ 100,\ 110,\ 111,\ 011,\ 001,\ 000

不同串共有 6 种:

000, 100, 110, 111, 011, 001000,\ 100,\ 110,\ 111,\ 011,\ 001

所以输出 66。