传送门
题解：
考虑怎么做这道题。
首先发现性质：
改变次数=2×总操作数−答案中′1′的个数" role="presentation">改变次数=2×总操作数−答案中′1′的个数改变次数
题目链接：传送门
题解：不难发现，我们有一个优秀的N2N^2的dpdp做法，记录f(i,j,0/1)f(i,j,0/1)表示ii子树内选jj个，当前根选没选。
我们要知道分治NTTNTT的复杂度：对于kk个总度数∑deg=k\sum deg=k的多项式来说，计算它们乘积的复杂度可以做到：O((∑deg)log(∑deg)logk)O((\sum deg)log(\sum deg)logk)。
因此，我们采用重链剖分，先转移所有轻链。
不难发现，
g(u,0)=∏v∈son(g(v,0)+g(v,1))g(u,0)=\prod_{v\in son} (g(v,0)+g(v,1))
Easy RainForecast
题意：n" role="presentation" style="position: relative;">nnn个人依次传递一个布尔变量，第i" role="presentation" style="position: relative;">iii个人有pi" role="presentation" style="position: relative;">pipip_i的概率传错，问最后结果正确的概率是多少。n≤50" role="presentation" style="position: relative;"&
Easy DigitStringDiv1
题意：给一个串s" role="presentation" style="position: relative;">sss，给定数x" role="presentation" style="position: relative;">xxx，现在擦除s" role="presentation" style="position: relative;">sss的一些字符，问有多少种擦除方法使得s" role="presentation" style="position: relative;">sss组成的数字严格大于x" role=
Easy BalancingTrees
题意：给你一棵树，有N" role="presentation">NNN个点，称一棵树为平衡的当对于一棵树的每一个节点来说它的儿子的子树权值和都一样。现在每个点有个权值wi" role="presentation">wiwiw_i，每次可以把一个点的权值+x/−x" role="presentation">+x/−x+x/−x+x/-x，代价为x" role="presentation">xxx。问最少花多少代价让这棵树平衡。x∈R,N≤250,wi&#x
Easy Lilypads
题意：一个n×m" role="presentation" style="position: relative;">n×mn×mn\times m的池塘，每一个格子有一片荷叶，一只青蛙从(x,y)" role="presentation" style="position: relative;">(x,y)(x,y)(x,y)开始跳，每一次可以向四个方向中的任何一个方向跳任意距离，但是不能两次往同一个方向跳，输出一种方案让青蛙经过每个格子恰好一次。 n,m≤50" role="presentation" sty
A Fairness
题意：三个人做游戏，每个人开始有一个数A,B,C" role="presentation" style="position: relative;">A,B,CA,B,CA,B,C。每一次一个人会用其它两个人的数的和替换自己的数，做k" role="presentation" style="position: relative;">kkk次操作，问最后A" role="presentation" style="position: relative;">AAA的减去B" role="presentation" style="position: relati
Easy ResistorFactory
题意：你一开始的产品只有1" role="presentation" style="position: relative;">111欧姆的电阻
你可以制造一些产品，每个产品都是之前产品的串联或者并联。
现在你要造出d/109" role="presentation" style="position: relative;">d/109d/109d/10^9欧姆的等效电阻。d∈[0,1018]" role="presentation" style="position: relative;">d∈[0,1018]
Easy MaximizingGCD
题意：给你2n" role="presentation" style="position: relative;">2n2n2n个数，问把他们两两配对求和形成的n" role="presentation" style="position: relative;">nnn个数gcd" role="presentation" style="position: relative;">gcdgcdgcd最大是多少。n≤30,a≤109" role="presentation" style="positio
Easy MostFrequentLastDigit
题意：构造一个长为n" role="presentation" style="position: relative;">nnn的数列，满足两两的和mod 10" role="presentation" style="position: relative;">mod 10mod 10mod\ 10为d" role="presentation" style="position: relative;">ddd的整数对唯一最多，不能有一样多的。要求每个数都不一样，不超过109" role="
Rockdu's Blog