无语的智商题啊.居然没人写题解. 首先dp打个表.cnt[i]表示大小为i的二叉树的总个数.当然这个就是catlan数.然后son[i]表示大小为i的所有不同构的二叉树的叶子数的和. 然后经过找规律(翻oeis)发现son[i] = C(2n-2,n-1). 于是就没有于是了.推一下组合数发现answer=n2(n+1) / (n2) / (n*2-1). 代码好无语.

比较基础的期望+高消的题.为了说明一下高消是what,我决定写一发题解. 首先题意是有个n个点m条边的无向图.有两个人初始位置是a和b.每个时刻每个人在一个点有p_i的概率不动,否则等概率移动到相邻的点.只有在同一时刻在同一个顶点上才算相遇.相遇了他俩就玩去了.求在第i号点相遇的概率. 首先方程很好列.定义一个状态f[i][j]表示第一个人在i,第二个人在j的概率.那么f[i][j] = ∑ f[k][l] * ptrans(k,i) * ptrans(j, l),其中ptrans(a,b)表示从a移动到b的概率. 然后这个东西就用高消嘛.(upd:才发现它叫gauss而不是guess.捂脸ing) 高消就是说每次把剩下的方程里的第一个系数不为0的未知数的系数全部通过减某一个方程来把这个系数都消成0.当然被减的方程得留下系数过会再用于推答案.然后就可以不管这个被留下的方程了. 换句话说,如果把方程组看成t*(t+1)的矩阵的话,其实就是消成一个右上三角. 然后再倒着推出每个未知数的值. 这个直接算比例就完了嘛.然后有一种情况是当前a[i][i]已经为0了,那么减不掉?反正所有方程的顺序没有关系啊.你就随便找一个不是0的到前面来消就好了啊.如果剩下方程的这一个系数都是0,那这个未知数取啥就无关了.也无所谓啦. 详见代码.

apio的题也是比较有质量的.听说这题很难写但是我感觉难点在想上啊. 首先直接两遍Lis强行判断能不能扔进去是错的.至于为啥我也不造啊. 于是就是区间询问答案最大.然后每次看把当前询问加进去后会不会对最大答案产生影响. 然后发现有点像今年sctsc那个倍增?居然还真是倍增.先去掉包含有其它区间的区间.然后找每个点向右跨过的最近的一个区间.然后再倍增一发. 好神的做法啊ovo btw为啥bzoj第一页上充满了黑坨坨.不爽Ing.

之前在哪里听过的题啊.于是卡了一晚上. 就是缩个点然后看看哪些点必需自己去点第一把火就好了. 然后有一种情况是把剩下的都查完之后只剩下一个了.那么看存不存在这种情况.那就是某个第一把火的地方的scc大小为1,且它连出去的都不必需用它查. 然后我就卡在ans>1上了.我傻了ovo 然后非递归tarjan还是写得不熟啊.还要再加深一下对自己想出来的算法的印象.

bzoj都3k道题了ovo hnoi的题好强. 这个题就建反图然后跑topsort就行了.每次选能选的里最大的扔进去.最后倒过来输出. 我也是猜的然后交上去居然是对的. 为什么呢?好神奇?

三维算几ovo给mhy和idy跪烂. 三维凸包算是一种比较简单的三维算几吧.首先有一些基本的公式比如算四个点的体积就是一个底*高.不过变成了一个面的法向量点乘另一个向量. 然后就用随机增量法每次替掉一些面就好了. 然后有一种可能是所有点都共面.这种时候就随机把一些点乱移动一下让它们形成一个高度和纸一样薄的凸包再来算就行了. 感觉也不是特别恶心啊ovo

在颓废了一天之后决定写一个题解.因为我觉得这题挺有意思. 我们需要转化一下式子.把原来的a,b改成A,B.设d=gcd(A,B),A=ad,B=bd. 那么(a+b)d | abd2,即(a+b)|ab*d. 又因为gcd(a,b)=1,所以(a+b)一定与a,b都互质.于是(a+b)|d. 设t*(a+b)=d.那么因为bd≤n,所以t(a+b)*b≤n.那么b是sqrt(n)级别的.且我们只需要统计三元组(a,b,t)的个数就行了. answer=∑b∑a(n/b)/(a+b)(gcd(a,b)=1)然后这个玩意看上去好像是个长得怪异一点的狄利克雷卷积啊. 于是就是要求[l, r]中与b互质的数的个数?这个玩意等于∑i|bu(i)*(r/i).然后发现可以把b分解质因数.而且只留下u不为0的.于是就能出奇迹辣好厉害ovo

好玩的数论题。想想发现可以像快速幂一样跑。然后就是思考如何转移优化。 发现模数比较奇怪。居然是fnt的模数ovo那就要用fft喽？可是这里是乘啊。木有关系喽，因为m是素数，所以它一定有原根。于是可以取原根的幂次，就变成加辣。 这种东西我自己当然想不出来ovo 同余系下的东西真有趣ovo

之前听说是异或高消？好神的感觉。 然后可以树形dp嘛！为啥网上题解这么误导ovo 就是f[u][i][j]表示u这个点有没有亮，有没有被按开关。完了嘛。 无语了辣。

比较神奇的数学题.首先你得听说过一个东西叫Mertens函数.于是你可以找到一篇论文.然后你发现它是英文的.试图理解了很久没有成功. 然后终于有人良心贴出了一个blog.这回懂辣开心ovo 其实就是那一个公式:F(n) = ∑一堆约数 + ∑k=2nF([n/k]) 然后发现mu和phi的左边一堆都是可以O(1)算的辣.右边强行记搜可以做到O(n2/3)的辣. 然后手写个hash啥的就能跑得飞快的辣.