原文链接www.cnblogs.com/zhouzhendong/p/ZJOI2019Day1T2.html在LOJ交了一下我的代码，发现它比选手机快将近4倍。对于线段树上每一个节点，维护以下信息：1.这个点为1的概率。2.这个点为0，且它有祖先是1的概率。其中，第一种东西在维护了2.的情况下十分好求。第二种东西，只有...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ449.html设f(i)表示给i只鸽子喂食使得至少一只鸽子被喂饱的期望次数，先min-max容斥一下。（$fracni$表示期望每$fracni$步喂这i只鸽子一次）$$ans=sum_{i=1}^n(-1)^{i+1}inomnifrac...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ103.html　　我终于会PAM啦　　感谢CLY大佬手把手教我PAM　　建个PAM。　　统计一下每一个节点的Right集合大小，设size[x]为节点x的right集合大小。　　求出max(len[x]*size[x])，做完了。#inclu...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ348.html第一次知道子集卷积可以自己卷自己。这是一道子集卷积模板题。设$sum[S]$表示点集S的点权和。设$f[S]$表示对点集S进行州区划分得到的答案，定义$g[S]$在点集S合法时为$(sum[S])^p$，不合法时为0。则$$f[...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ370.html首先易知答案肯定是一条链，因为挂在链的最下面肯定比挂在其他节点上赚。问题被转化成了从一个集合中不断选数加入到当前序列尾端，使得序列的所有前缀AND之和最小。我们发现，假如加入一个数后可以使序列的AND值变小，那么必然不会去加一个...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ24.html　　我们将C型车站称为左括号'('，D型车站称为右括号')'，设括号i的位置为p[i] 。　　首先，我们用点0把所有位置都询问一遍，那么距离最近的那个点一定是在0右边的第一个')'。　　设0位置为x，距离0最近的）为y，...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ373.html　　真是一道毒瘤题。UOJ卡常毒瘤++。我卡了1.5h的常数才过QAQ　　Orzjry　　标算居然是指数做法。1.感受一下线图上点的含义1.1一阶线图　　L(G)上的一个点对应G中的一条边。1.2二阶线图　　$L^2(G)$上一...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ75.html根本没想到。首先我们可以考虑一种做法：找一些图，使得他们各自的生成树个数乘起来等于k。那么只要将他们用一条链连起来就得到答案了。接下来考虑如何得到这些图。 考虑随机生成一个n个点的图，它的生成树个数最大是$n^{n-2}...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ349.html被cqzD没了。我Dcly关你啥事（逃首先链的情况直接rand就好了。期望次数$O(n+logn)$。然而我一开始写挂了。 开始扯淡我用这个模数，就可以过原题数据：('C'+'L'+'Y'+'A'+'K...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ7.html这题是Unknown的弱化版。如果这个问题出在序列上，那么显然可以CDQ分治+斜率优化+凸包上二分来做。那么它出在树上？点分治。写挂了好多地方调了好久，自闭了。#pragmaGCCoptimize("Ofast","...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ394.html首先我们发现一个数不能既被往左换又被往右换。也就是说不能有任何一个数左边有比他大的，又被有比他小的。也就是最长下降子序列长度不超过2。所以我们一定可以找到2个上升序列包含所有的数。于是容易想到$O(n^2)$的d...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ424.html主席太神仙了！首先我们把题意转化成：对所有挺好序列建笛卡尔树，有多少笛卡尔树互不同构。容易推出dp式子：$f[i][j]$表示$j$个数，他们的max为i。$$f[i][j]=sum_{k=0}^{j-1}f[i...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ266.html首先我们可以直接暴力$O(n^2)$用sg函数来算答案。对于一个树就是枚举一下从根出发到哪一个节点为止的路径被删掉了，剩下所有的子树的sg值xor起来，对于每一个路径后的答案取一个mex。我们考虑快速的做这个过程...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ450.html首先有一个东西叫做“单位根反演”，它在FFT的时候用到过：$$frac1nsum_{i=0}^{n-1}omega_n^{dcdoti}=[n|d]$$其中$omega_n$表示$n$次单...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ41.html首先写个乱搞：一开始每一行都选择第一个非0元素，然后，我们对这个方案不断做更新，直到任意两行选择的值不同。更新方法：如果有两行选了相同的值，那么让靠前的那行选择后一个非0的值。交上去。过了。wtf？然后发现证明这个...