CTime_Pup_314

题目描述

长期以来，中心市的水没有什么问题。城市的下水道系统是一种有根树结构：中央水库位于树的根节点，房屋位于树的叶节点。水从中央水库通过管道延树边流向每间房屋，所有房屋都可以使用到水。

突然，强盗们占领了一些房屋。作为市长，你非常忧虑并且想要驱逐这些强盗。所以，你打算停止向那些强盗占领的房屋供水。为此，你可能需要阻断下水道系统的某些管道。如果从水库到某房屋的路径中至少有一条被阻断的管道，那么该房屋将无法取水。

题目描述

你已被气候测量协会聘用，该协会是致力于追踪全球气候在长时间内变化趋势的科学组织。 当然，这绝非易事。 他们在世界各地部署了许多小型设备，旨在对当地天气状况进行定期测量。 这些是廉价的设备，它们的功能受到某些限制。每天，它们观测一次可能会发生于当天的四类标准天气中的一种：$Sunny$、$Cloudy$、$Rainy$ 或 $Frogs$。每进行 $n$ 次观测之后，将结果报告给主服务器进行分析。但是，大量的设备导致可用的通信带宽过载。协会需要你帮忙提出一种压缩这些报告序列位数的方法。

希望不要丢人

由于集训队作业出来了，所以这篇文章就不再更新了QwQ

$\bullet$ 是抄的题解

10.8

[PKUWC2018]随机游走 $\bullet$

显然用 $min-max$ 容斥将所求变成到达一个点集的最早期望时间。考虑最早时间如何求出，对于一个点集 $S$，不妨设 $f_x$ 为 $x$ 内的点到 $S$ 的最早期望时间。

div

首先我们有一个十分简单的式子

$$\mathrm{E}(n)=\frac{1}{{\sigma }_0(n)}\sum _{d|n}E(d)+1$$

其中 ${\sigma }_0$ 为约数个数

化简之后得

最近突然想做多项式了，就找了些题，这道题用的 2D-FFT 的科技我还不会

首先和式的 $i$ 和 $j$ 除了出现在下标上，就是出现在指数上，并且 $490019$ 是一个质数 $\phi (490019)=490018=2\times 491\times 499$ 我们就可以想到按照 $i^2{j}^3$ 模这些数的值的余数来计算，即答案为

深知自己快退役了，所以这段时间打算把 FFT 原理的那一部分搞明白

首先，我们需要知道平常我们做的 FFT 实际上是循环卷积，循环卷积的长度相当于单位根的下指标，而平时这个值都是大于最后次数的，所以和普通卷积并无差别，具体来说我们要求的是

$$c_k=\sum _{i=0}^{n-1}\sum _{j=0}^{n-1}{a}_i{b}_j[(i+j)\mathrm{mod}n=k]$$

由单位根反演可得

很显然，设答案序列为 $a$ 则有

$$a_t=\sum _{i=0}^L(\genfrac{}{}{0ex}{}{L}{i})w_{x,y}^i[i\mathrm{mod}k=t]$$

由单位根反演

$$[n|k]=\frac{1}{n}\sum _{i=0}^{n-1}{\omega }_n^{ki}$$

所谓类欧几里得就是复杂度与欧几里得算法类似，但其他完全不一样的算法

开始之前，先做一个简单的约定，其中 $0^0=1$

$${\mathrm{S}}_{\mathrm{m}}(n)=\sum _{i=0}^n{i}^m$$

P5170 【模板】类欧几里得算法

设题目中所要求的为

$$\begin{array}{rl}& \mathrm{f}(a,b,c,n)=\sum _{i=0}^n\lfloor \frac{ai+b}{c}\rfloor \\ \\ & \mathrm{g}(a,b,c,n)=\sum _{i=0}^n\lfloor \frac{ai+b}{c}{\rfloor }^2\\ \\ & \mathrm{h}(a,b,c,n)=\sum _{i=0}^{n}i\lfloor \frac{ai+b}{c}\rfloor \end{array}$$ 我们先从 $\mathrm{f}$ 入手

Jump

题目描述

求 $n$ 个点 $m$ 条边的无向图，求可将每个边定向的方案满足最后的图是 DAG 的方案数