求此题思路（XJOI 7719）

Question

先看题目：
题目描述：
有n个人站成一排，编号为1-n，现在将他们分成多组，每组的人的编号都是连续的(如3,4,5是连续的;1,3不是连续的)，每组的人数不为空。问有几种分法
输入格式：
输入一个整数n
输出格式：
按题目描述输出
样例输入1：
4
样例输出1：
8
约定：
N<=5000
感觉题目没怎么看明白，迷迷糊糊

Answer 1

先给LZ解释一下题目的意思。
假设现在有4个元素1,2,3,4排成1列，那么有多少种不同的集合取法呢：
第一种: {1},{2},{3},{4}
第二种: {1},{2},{3,4}
第三种: {1},{2,3},{4}
第四种: {1,2},{3},{4}
第五种: {1,2},{3,4}
第六种: {1,2,3},{4}
第七种: {1},{2,3,4}
第八种: {1,2,3,4}
请注意像{1},{3},{2,4}这样的分法是不合适的，因为{2,4}不是先后相连的同一串。
那么要怎么求总共的数量呢？
仔细观察就可以发现，当我们把一个解譬如{1},{23},{4}摆出来的时候，其实等价于在原数列
1,2,3,4上砍了2刀，一刀砍在1,2之间，另一刀砍在3,4之间，于是原数列就被 分成了1,23,4这样3段。
所以，所谓的有几个不同的解，就是我们有多少种不同的砍法。
换言之，就是我们可以在原数列中选择若干个逗号“,”进行切割，这样的逗号的选法有多少种。
第一种比较笨的解法是：n个数列一共有n-1个逗号，
我们可以有
选择0个逗号一共有C(n-1,0)种选法，
选择1个逗号一共有C(n-1,1)种选法，
选择2个逗号一共有C(n-1,2)种选法，
...，
选择n-1个逗号一共有C(n-1,n-1)种选法，
所以总共有C(n-1,0)+C(n-1,1)+C(n-1,2)+...+C(n-1,n-1)个解。
如果你熟悉二项式(a+b)^k的展开式C(k,0)a^0xb^n+C(k,1)a^1xb^(n-1)+C(k,1)a^2xb^(n-2)+...+C(k,k)a^kxb^0的话，用n-1代替k，并令a=b=1，可以有C(n-1,0)+C(n-1,1)+C(n-1,2)+...+C(n-1,n-1)=2^(n-1)。

另外一种比较聪明的解法是，我们把这n-1个逗号排起来，选中要切割的标上1，没有选中的标上0，结果就是一个n-1位长度的二进制数，这样的二进制数一共有2^(n-1)个，所以有2^(n-1)种解法。