然而高精度是硬伤。。。

采用常规的数学归纳法
假设第n天的蘑菇总数是C(n,k)，其中k是最接近n/2的整数，考虑第n+1天的蘑菇数，分两种情况讨论
如果n是奇数，自然有k=(n-1)/2，那么不难推得这时所有的蘑菇长度都是偶数
它们下一天都会分裂成2只蘑菇
因此第n+1天的蘑菇数量就是2C(n,k)
而由组合数的性质可知C(2k+2,k+1)=2C(2k+1,k)
因此第n+1天的蘑菇数也满足公式。
如果n是偶数，自然有k=n/2，这时所有的蘑菇长度都是奇数
那么下一天，仅有长度为1的蘑菇变为长度为2的蘑菇，其余蘑菇都是一分为二
因此，若设长度为1的蘑菇有x个，则第n+1天蘑菇总数为x+2(C(n,k)-x)=2C(n,k)-x
下面重点计算x
我们知道，x表示的是第n天（即第2k天）长度为1的蘑菇的总数
我们假象增加一个第0天，第0天仅有一只长度为1的蘑菇，这不影响问题本身，因为第1天就恰好有一只长度为2的蘑菇
每只蘑菇可以对应一个长度为2k的加号和减号组成的序列，其中加号表示这一天这只蘑菇是由长度d分裂到了d+1，而减号表示这一天这只蘑菇是由长度d分裂到了d-1
例如，第5天所有蘑菇长度如下
+++++ 长度6
++++- 长度4
+++-+ 长度4
++-++ 长度4
+-+++ 长度4
+++-- 长度2
++-+- 长度2
++--+ 长度2
+-++- 长度2
+-+-+ 长度2
注意到从最左边开始向右数的过程中，一旦有一个状态，加号的数量小于减号的数量，则这只蘑菇在这一天的长度即为0或负数，即这只蘑菇实际上并不存在
那么第2k天长度为1的蘑菇个数x，就等于长度为2k的加减序列中，加号与减号数量相同，且保持从左至右一直是加号个数不小于减号个数的序列数
这个数就是熟知的卡特兰数，其值为C(2k,k)-C(2k,k-1)
代入到上面式子，知n+1天蘑菇总数为2C(2k,k)-[C(2k,k)-C(2k,k-1)]=C(2k,k)+C(2k,k-1)=C(2k+1,k)，也符合公式
由数学归纳法可知，上面的结论对所有的n都成立

官方数据过了，打个表

大神给了公式，我也没什么好说的了。。一个看起来很复杂的东西就这样被骗分~

gets ；cin.get；cin.getline; getline; 之间有哪些是允许用的考试时

我没有被坑~我直接排序再查找。

我没有被坑~我直接排序再查找。

我终于知道我为什么这么这么长时间没有通过了！只能过第二个点的原因是——gets()读取字符串时，会把换行符也给带上！

自不量力的交了冒泡排序、选择排序和插入排序，最终结果就是全错。。。
还是快排是王道！

第一遍仪器标号忘-m了....又没有1A不开心...

烤馍片算法的修改一下就可以了。。
注意几个坑爹的地方：
1.字符串的可能分成了好几行。
2.输入文件名错了的话是会爆T而不是R（好吧，只有我这种沙茶才可能犯这种错误）

回复 @殇浸雪，奕流��，亦真亦冥玄无穷 :
抄题解都改跪了，orzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz

强大的基数排序

我看模拟抱着AC希望的人还不少

这题居然用到了置换群的性质。。。
不看题解真的想不到

突破1000分留念

这题好诡异。。我的程序对
3 2
1 1 1
这样的测例会输出3，但依然AC。看来"1+1"和"1+1"也不见得是一种情况。

插头DP+哈希判重+高精度
毒瘤三件套凑齐了