0%

题目描述

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

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

阅读全文 »

题目描述

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

阅读全文 »

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

\(\color{red}{\bullet}\) 是抄的题解

10.8

[PKUWC2018]随机游走 \(\color{red}{\bullet}\)

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

阅读全文 »

div

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

\[ \operatorname{E}(n)=\frac{1}{\sigma_0(n)}\sum_{d|n}E(d)+1 \]

其中 \(\sigma_0\) 为约数个数

化简之后得

阅读全文 »

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

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

阅读全文 »

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

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

\[ c_k=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}a_ib_j[(i+j)\operatorname{mod}n=k] \]

由单位根反演可得

阅读全文 »

很显然,设答案序列为 \(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}\) 入手

阅读全文 »

Jump

题目描述

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

阅读全文 »