题目描述
长期以来，中心市的水没有什么问题。城市的下水道系统是一种有根树结构：中央水库位于树的根节点，房屋位于树的叶节点。水从中央水库通过管道延树边流向每间房屋，所有房屋都可以使用到水。
突然，强盗们占领了一些房屋。作为市长，你非常忧虑并且想要驱逐这些强盗。所以，你打算停止向那些强盗占领的房屋供水。为此，你可能需要阻断下水道系统的某些管道。如果从水库到某房屋的路径中至少有一条被阻断的管道，那么该房屋将无法取水。
[WF2015L]Weather Report
题目描述
你已被气候测量协会聘用，该协会是致力于追踪全球气候在长时间内变化趋势的科学组织。 当然，这绝非易事。 他们在世界各地部署了许多小型设备，旨在对当地天气状况进行定期测量。 这些是廉价的设备，它们的功能受到某些限制。每天，它们观测一次可能会发生于当天的四类标准天气中的一种：\(Sunny\)、\(Cloudy\)、\(Rainy\) 或 \(Frogs\)。每进行 \(n\) 次观测之后，将结果报告给主服务器进行分析。但是，大量的设备导致可用的通信带宽过载。协会需要你帮忙提出一种压缩这些报告序列位数的方法。
绝对做不完的IOI2021集训队作业
希望不要丢人
退役前的做题记录
由于集训队作业出来了，所以这篇文章就不再更新了QwQ
\(\color{red}{\bullet}\) 是抄的题解
10.8
[PKUWC2018]随机游走 \(\color{red}{\bullet}\)
显然用 \(\min-\max\) 容斥将所求变成到达一个点集的最早期望时间。考虑最早时间如何求出，对于一个点集 \(S\)，不妨设 \(f_x\) 为 \(x\) 内的点到 \(S\) 的最早期望时间。
20200225模拟赛
div
首先我们有一个十分简单的式子
\[ \operatorname{E}(n)=\frac{1}{\sigma_0(n)}\sum_{d|n}E(d)+1 \]
其中 \(\sigma_0\) 为约数个数
化简之后得
CF1054H Epic Convolution
最近突然想做多项式了，就找了些题，这道题用的 2D-FFT
的科技我还不会
首先和式的 \(i\) 和 \(j\) 除了出现在下标上，就是出现在指数上，并且 \(490019\) 是一个质数 \(\varphi(490019)=490018=2\times491\times499\) 我们就可以想到按照 \(i^2j^3\) 模这些数的值的余数来计算，即答案为
[CTSC2010]性能优化
深知自己快退役了，所以这段时间打算把 FFT
原理的那一部分搞明白
首先，我们需要知道平常我们做的 FFT
实际上是循环卷积，循环卷积的长度相当于单位根的下指标，而平时这个值都是大于最后次数的，所以和普通卷积并无差别，具体来说我们要求的是
\[ c_k=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}a_ib_j[(i+j)\operatorname{mod}n=k] \]
由单位根反演可得
[HNOI2019]白兔之舞
很显然，设答案序列为 \(a\) 则有
\[ a_t=\sum_{i=0}^L\binom{L}{i}w^i_{x,y}[i\operatorname{mod}k=t] \]
由单位根反演
\[ [n|k]=\frac{1}{n}\sum_{i=0}^{n-1}\omega_n^{ki} \]
确实学不会的类欧几里得算法
所谓类欧几里得就是复杂度与欧几里得算法类似，但其他完全不一样的算法
开始之前，先做一个简单的约定，其中 \(0^0=1\)
\[ \operatorname{S_m}(n)=\sum_{i=0}^ni^m \]
P5170 【模板】类欧几里得算法
设题目中所要求的为
\[ \begin{aligned} &\operatorname{f}(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor\\\\ &\operatorname{g}(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor^2\\\\ &\operatorname{h}(a,b,c,n)=\sum_{i=0}^ni\lfloor\frac{ai+b}{c}\rfloor \end{aligned} \] 我们先从 \(\operatorname{f}\) 入手