斯特林数

http://baike.baidu.com/link?url=kw5Kxe3nSvRJR0TpJUpMrORcQL8fyZFpJlT9_o0RlGYOy0bKFobabPPSj3LxGfy7o1qGVycrYK4Iags3hMFq0a 在组合数合里，贝尔数给出了集合划分的数目，以数学家埃里克·坦普尔·贝尔（Eric Temple Bell）命名，是组合数学中的一组整数数列。[1] 以B0= B1=1为始， 首几项的贝尔数为：1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, …（OEIS的A000110数列） _B__n_是基数为_n_的集合划分数目。集合S_的一个划分是定义为_S_的两两不相交的非空子集的族，它们的并是_S。例如_B_3 = 5因为3个元素的集合{a, b, c}有5种不同的划分方法：

先预处理出来比小于等于n的素数的个数和回文数的个数… 素数不筛竟然也可以过 然后暴力就好. 需要注意的是，比值并不单调，找最大的n，可能之前某个数开始不满足条件，之后又有满足条件的了.

比赛的时候想到了是dp搞… 不过dp废….. 可能更多的是心理上… 这道题并不怎么难想，但是以觉得是dp，就给了自己一种暗示…这题我搞不出来…

因为字母的排列顺序是任意的，所以判断能否形成回文串的条件就成了出现次数为奇数的字母的个数是否大于1个，如果是，那么一定不能形成回文串，否则一定可以. 为了找到以节点v为根的 subtree 中深度为h的后代，需要求出dfs序列，并且记录每个节点初次访问的时间戳和离开它的时间戳，然后二分.