分割数

把有n个元素的集合分割成一个或多个子集的方式总数称为n阶分割数。

例如4阶分割数为5，因为有4个元素的集合可以用以下五种方式分割: \begin{align*} &4 \\ &3+1 \\ &2+2 \\ &1+2+1 \\ &1+1+1+1 \end{align*} 从$n=0$开始打印前100个分割数，每个数一行。

注：原题题面的表述未定义$n=0$的情况，若按原题表述结果应从1,2,3,5,7...开始而非答案中的1,1,2,3,5,7...。此处按正确的定义作了修正。

本题难度:

解答

以下代码按OEIS A000041中的递归公式和代码缩写。

查询了sympy的源码，也并没有更好的方法。

由于需要作记忆化搜索，似乎很难压缩码量。

最终代码有八行。

代码长度：172字节 vs. 全站第一：55字节。

from functools import *
@cache
def f(n):
  if n<2:return 1
  s,j,k=0,n-1,2
  while j>=0:t=f(j);s+=[-t,t][k//2&1];j-=[k//2,k][k&1];k+=1
  return s
*map(print,map(f,range(100))),