P0826

[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,\ldots,x_n) 表示。

在 nn 维空间中，两点 (x1,x2,…,xn)(x_1,x_2,\ldots,x_n) 与 (w1,w2,…,wn)(w_1,w_2,\ldots,w_n) 之间的欧氏距离定义为

d=(x1−w1)2+(x2−w2)2+⋯+(xn−wn)2.d=\sqrt{(x_1-w_1)^2+(x_2-w_2)^2+\cdots+(x_n-w_n)^2}.

在 nn 维空间中，花仙子每次施展魔法时，都会任意选择一个参考点 (w1,w2,…,wn)(w_1,w_2,\ldots,w_n) 和一个作用半径 rr。空间中所有与该参考点距离严格小于 rr 的花，都会受到此次魔法的影响。

每次魔法都会为受到影响的花带来一种不同的属性，并且多次魔法的效果可以叠加。若花仙子一共施展了 mm 次魔法，则位于空间中某点的花所具有的属性，可以用长度为 mm 的二进制串 a1a2…ama_1a_2\ldots a_m 表示。对于 1≤i≤m1\le i\le m，若该花受到第 ii 次魔法的影响，则 ai=1a_i=1；否则 ai=0a_i=0。

不同的属性对应不同种类的花。请计算花仙子在 nn 维空间中施展 mm 次魔法后，最多能够得到多少种不同的花。

输入格式

输入包含两个以空格分隔的整数 mm 和 nn，分别表示花仙子施展魔法的次数和空间的维数。

输出格式

输出一个整数，表示花仙子在 nn 维空间中施展 mm 次魔法后，最多能够得到的不同花的种数。

样例输入

3 1

样例输出

6

数据范围

  • 1≤m≤1001\le m\le 100；
  • 1≤n≤151\le n\le 15。

来源与许可

本题为 HNOI 2006 试题「花仙子的魔法」，题面与测试数据整理自 BZOJ。

样例 1

输入

3 1

输出

6