感觉我好慢。。
UPD:常数优化，效果拔群（其实我第一遍交的时候不知道count()这个函数，居然n^2统计答案）

前排

感谢Yveh,DaD3zZ大神提醒，该题只用一个（两个）log就可以做，两个（三个）log的标程已替换成一个（两个）log的，时限改为1s
求管理重新审核
（又一次）身败名裂.jpg

这种题能错这么多次我真是弱爆..........

回复 @DaD3zZ :
这种使代码达到最差复杂度的数据要怎么造呀……

回复 @kito :
恩，我问了一下吉老师，这种做法最差还是log2的..
不过除非构造不然很容易就全部一样了..所以效果效果比log2快很多..

全oi就这一个题是构造吗

回复 @DaD3zZ :
吉老师不是说随机数据下全局and 全局or很快整个序列都会变成一样的么，估计是这个原因吧。

回复 @小一米 :
这样的O（1）合并的复杂度应该才是最坏log2的吧..
log合并是log3的吧..
感觉每一位都有O(N)段，一共log位，所以一共NlogN段，每一段在线段树上都是log
但是感觉随机数据表现应该非常优秀...

和2570差不多

回复 @‎Alboi_真神名��驴蛋蛋 :
我需要的做法计算C(k-1,n+k-1)……这个显然要用(n+k-1)!/((k-1)!n!)了。于是求逆的问题就出来了。
好吧我直接求的K次前缀和的系数向量，您应该是求的一次前缀和的向量之后求幂，所以我的做法除了NTT其他都是线性的，因此常数稍微小一点吧……

回复 @kito :
大爷常数好小啊QwQ，压不过您QwQ

回复 @FoolMike :
求逆？啥求逆？

k出的比模数还大，这是要卡求逆的节奏吗？
如果我们碰到p的倍数一概不乘就好了嘛！最后总是会消掉的……这样就卡不掉离线打表了。

%%%

回复 @yveh :
不胜感激。

回复 @kito :
那这样常数更优越了。

回复 @yveh :
嗯，我是在合并same的时候多了一个log，这个log可以用位运算直接与掉，谢谢。
我是把与和或操作转化成了区间减值和区间加值，可以只用一个lazy标记。

回复 @kito :
因为判断可以是O(1)啊，而且or和and可以O(1)合并