原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ36.html按照$k$分类讨论：k=1:我们考虑每一位的贡献。若有至少一个数第$i$位为$1$，则对答案的贡献为$2^i/2$。k=2:发现每个异或和的平方为$sum_isum_j2^{i+j}bit_ibit_j$。那么考虑...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ314.html　　如果只加不减，那么瞎势能分析一波可以知道暴力模拟的复杂度是对的。　　但是有减法怎么办？？？　　再搞一个类似的，维护减了多少。　　那么，询问一个数位的值的时候，我们只需要得到两部分值中这一位的值是多少，以及是否...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ195.html　　首先询问都可以放到最后处理。　　对于操作，我们把它差分一下离线下来。　　现在的问题就是从第一棵树到第n棵树扫一遍，并不断维护树的形态。　　容易感受到这棵树会有删节点之类的操作，所以自然想到LCT。　　但是要涉...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ347.html　　有三棵树，边有边权。　　对于所有点对(x,y)求在三棵树上x到y的距离之和的最大值。　　点数<=100000　　我自闭了。　　在此之前，我没写过边分治，只写过一次虚树。　　我自闭了。 　　一棵...

原文链接https://www.cnblogs.com/zhouzhendong/p/IOI2018Day1T1.html　　首先二分一下，花费2次操作求出第一位的字符。　　假设第一个字符是Y，答案字符串的长度为i-1的前缀是S，我们考虑如何只花费1次询问得到下一个字符。　　press(SAA,SAB,SAX,SB)-...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ275.html用卢卡斯定理转化成一个k进制意义下的数位dp即可。算答案的时候补集转化一下会好写一些。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongL...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ62.html太久没更博客了，该拯救我的博客了。$$sum_{1leqjleqn}gcd(i,j)^{c-d}i^dj^dx_j=b_i\A_i=i^dx_i,B_i=frac{b_i}{i^d},f(x)=x^{c-d}\f(...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ53.html　　给定一棵有n个节点的树。　　每一个点有一个权值。　　对于每一个$i$给定三个参数$a_i,b_i,c_i$，从第$i$个点出发下一步能到达的点x需要满足以下三个要求之一：　　1.x在$a_i$到$b_i$的简单...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ207.html　　第一次听说LCT还可以维护子树信息。　　首先对于每一条路径rand一个值，分别放在两个端点上，于是询问一条边是否被所有路径的经过就变成了询问某一边所代表的子树是否包含所有路径的端点各一次。于是我求出子树xor...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ23.html　　给定一个有n个节点的仙人掌（可能有重边）。　　对于所有的$L(1leqLleqn-1)$，求出有多少不同的从节点1出发的包含L条边的简单路径。简单路径是指不重复经过任意一点。　　$nleq10^5$　　首先我们...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ33.html　　首先我们把问题转化成处理一个数组ans，其中ans[i]表示d(u,a)和d(v,a)同时为i的倍数的(u,v)个数。（最后求答案的时候只要莫比乌斯反演回来就好了。）　　注意一下我的代码中对于(u,v)有祖先关...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ269.html　　有一个多项式函数$f(x)$，最高次幂为$x^m$，定义变换$Q$：$$Q(f,n,x)=sum_{k=0}^nf(k)inomnkx^k(1−x)^{n−k}$$　　现在给定函数$...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ310.html　　给定$n$个数，请你选出两个不相交的集合（两个集合交换一下也算一种），问有多少种选择方案使得两个集合各自包含的数的异或值相等。　　不能两个都不选。　　$n,a_ileq10^6$　　首先，问题可以转化成：选择...

原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ3052.html　　给定一棵树，有$n$个节点。有$m$种颜色，第$i$个节点的颜色为$c_i$。　　给定参数$v_{1},v_2,cdots,v_m$和$w_1,w_2,cdots,w_n$，具有以下意义：　　　　第$i$...

原文链接http://www.cnblogs.com/zhouzhendong/p/9025092.html　　如果一个字符串可以被拆分为AABB的形式，其中AA和BB是任意非空字符串，则我们称该字符串的这种拆分是优秀的。　　现在给出一个长度为n的字符串S，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。...