Description

 

Input

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

Output

仅包含一个整数，表示花仙子在n维空间中实施了m次魔法后，最多能得到多少种不同的花。

Sample Input

3 1

Sample Output

6

 

无语的动态规划

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]的话，我认为是当新加一个i维的球时，可以把那个i维的球面看成是一个i-1维的空间，以前的j-1个球在这个i-1维的空间最多划分f[i-1,j-1]个区域

初始时，f[i,1]=2，f[1,i]=2*i或者f[0,i]=2

 

1 var 2     f:array[0..15,0..100]of int64; 3     n,m,i,j:longint; 4   5 begin 6     read(m,n); 7     for i:=1 to m do 8       f[0,i]:=2; 9     for i:=1 to n do10       f[i,1]:=2;11     for i:=1 to n do12       for j:=2 to m do13         f[i,j]:=f[i,j-1]+f[i-1,j-1];14     write(f[n,m]);15 end.