为什么要按右端点排序而不是左端点

完全不知道自己的高精度除法有没有写对就过了QwQ果然天佑啊

单调队列真~难~调！

没看见No和“连续”二字，以为是神题，狂wa

此人傻逼，请无视

回复 @<蒟蒻>我要喝豆奶 :

回复 @天地雨林 :
你不早说，QAQ

这个数据和官方数据不符，官方数据是牛被挤完奶一小时后才可以

写了好久QAQ

回复 @啊吧啦吧啦吧 :
压泥煤，压位是什么鬼

这道题C++语言的程序我最快，HAPPY！！

回复 @/k :
？？？？？

一天盖一层，有益身心健康

压6位就wa，压4位就ac……我也是醉喽……

然而高精度是硬伤。。。

采用常规的数学归纳法
假设第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; 之间有哪些是允许用的考试时