BZOJ3456 城市规划 – 2

题意

给出 $n$ ,请求出点数为 $n$ 的简单无向联通图个数

题解

之前这篇面讲了多项式对数的做法
这里讲个分治 NTT 的方法
设 $f_n$ 表示大小为 $n$ 的图的方案,那么枚举 1 所在的连通块大小,有转移:
$$
\begin{eqnarray}
f_i&=&2^{{i\choose 2}}-\sum_{j=1}^{i-1}{i-1\choose j-1}\cdot 2^{{i-j\choose 2}}\cdot f_j\\
&=&2^{{i\choose 2}}-(i-1)!\sum_{j=1}^{i-1}\frac{f_j}{(j-1)!}\cdot \frac{2^{{i-j\choose 2}}}{(i-j)!}
\end{eqnarray}
$$
继续阅读

BZOJ5323 游戏

题意

定义一种检查方法为从头到尾检查这个序列,检查完某个点后在它后面的标号是它的倍数的点都不用检查,设 $t(p)$ 为对于一个排列检查它需要多久
求对于 $[l,r]$ 共 $n=r-l+1$ 个数的所有 $n!$ 种排列,求出它们的 $t(p)$ 的总和模 $1e9+7$
例如对于序列 $\texttt{p=2 5 4 3 6}$ ,它的 $t(p)$ 为 $4$

题解

感觉这题很妙
可以发现,那些除了自己之外不会被其他的点给排除掉的位置才是需要去考虑的,不管其它的点怎么排
在例子里这种点就是 $\texttt{2,3,5}$
假设这样的点总共有 $m$ 个 继续阅读

SPOJ Count On Tree II

题目链接

题意

给出一棵大小为 $n$ 的树以及树上每个点的颜色,并且给出 $m$ 个询问 $(u,v)$ ,对每个询问求出 $u$ 到 $v$ 这条链上有多少不同的颜色
$n\leq 40000, m\leq 100000$

题解

第一次打树上莫队这东西
首先对于一条链的情况直接用普通莫队就可以解决
对于一棵树的情况,我们考虑如何将它转化为序列问题
可以使用欧拉序,我们将对每个点访问开始和结束时分别塞进序列里,就做出了欧拉序,例如样例
选区_155.png
对应的欧拉序就是
$\texttt{1 4 8 8 4 3 7 7 6 6 5 5 3 2 2 1}$ 继续阅读

BZOJ4237 稻草人

题意

给出 $n,(n\leq 2\times 10^5)$ 个点的坐标,求可以构成矩形左下角和右上角并且矩形中不包含任何其他点的点对个数

题解

分治+单调性
看题解都有点难看懂,但是看程序一下就看得懂
题解理性愉悦一下
首先按照 $x$ 坐标划分然后分治,考虑处理完两个子区间后怎么求当前区间答案
发现对于某个点 $(x,y)$ 我们找到最小的 $y_0$ 使得点 $(x_0,y_0)$ 满足 $x_0>x,y_0>y$ (对左边区间中的点考虑),那么该点在右边的合法配对点坐标只可能满足 $y< y_1< y_0$
那么我们将两个区间分别按照 $y$ 坐标排序,然后依次处理左边,对左边每个点计算右边有多少个点能和它配对 继续阅读

CF662C Binary Table

题目链接

题意

给出一个 $n\times m$ 的 $0,1$ 矩阵,可以选择一些行或列进行取反,矩阵中 $1$ 的个数最少可以是多少
$1\leq n\leq 20, 1\leq m\leq 100000$

题解

比较妙,我没想出来
发现 $2^n$ 枚举 $n$ 行的取反状态是可行的,但是这样之后应该怎么样快速计算贡献
考虑将每一列 $n$ 个 $0,1$ 由二进制转化为一个十进制数,然后将所有列按照这个数来分类考虑,称这个数为代表数
假设现在 $n$ 行的取反状态为 $S$ ,我们想求出此时的最小的 $1$ 的个数
设对于某个代表数 $i$ ,求出了在 $m$ 列中代表数为 $i$ 的列数有 $g_i$ 个
对于这个代表数 $i$ ,可以求出取反或不取反使得其中包含 $1$ 最少的个数 $f_i$
继续阅读

BZOJ5104 Fib数列

题意

在 $mod\ \ 10^9+\color{red}9$ 的意义下求出数字 $n$ 在 Fib 数列中出现在哪个位置
由于没有 spj如果有多个,输出最靠前的那个位置)

题解

之前 Picks 讲课的时候提到了这样一道题,但没说来源,所以我一直不知道网上有,后来乱逛时发现了这道题,做了一下
题解放在这篇文章的 T1 那里了
这里稍微讲一下模数为奇素数的二次剩余,使用 Cipolla 算法求解
现在要解决一个问题,给定 $n$ ,要求出模意义下的 $x$ 使
$$ x^2\equiv n\pmod{p} $$
或者说求 $\sqrt{n}\pmod{p}$
这里只是简要讲解,更详细的请到引用资料里看
继续阅读

OpenJ_POJ1055 Tree

题目链接

题面

以随机父节点的方式生成一棵节点个数不大于 $n$ 的随机树, 求平均结点深度的期望
$n\leq 10^{18}$

题解

又是 Picks 出的题
这题依然是好题
设前面已经生成 $i-1$ 个点,当前生成第 $i$ 个点,这个点的期望深度为 $d_i$ ,前 $i$ 个节点的期望平均深度为 $f_i$ ,则
$$
\begin{eqnarray}
d_i&=&f_{i-1}+1 \tag{1}\\
f_i&=&\frac{f_{i-1}(i-1)+d_i}{i} \tag{2}\\
\end{eqnarray}
$$
继续阅读

TsinsenA1221 大楼

题目链接

题意

给出一张带权图, 从 $1$ 结点出发, 问最少走过多少条边, 使得权值总和大于等于 $m$ 。
$1\leq n\leq 100, 1\leq m\leq 10^{18} $

题解

发现给出了一个邻接矩阵,而且从 $i\to k$ 和从 $k\to j$ 的权值和可以更新 $i\to j$ 的最大权值和
可以看做用邻接矩阵中 $g[i][k]+g[k][j]$ 来更新 $g[i][j]$
于是类似于矩乘的做矩阵快速幂棵快速得到走过 $l$ 条边的最大权值
继续阅读

单位根反演备忘录

之前 Picks 来讲课,结果 Guideposts 那题被 boshi 秒了 boshi讲完我还在下面懵逼
后来去学了单位根反演

单位根反演

具体来说,就是将 $[n\mid k]$ 转化为一个容易化简,求值,带入的式子
$$ [n\mid k] = \frac{1}{n}\sum_{i=0}^{n-1}\omega_n^{ki} $$

证明

  1. 当 $n\mid k$ 时,设 $k=t\cdot n$ ,则
    $$ \frac{1}{n}\sum_{i=0}^{n-1}\omega_n^{ki} = \frac{\sum_{i=0}^{n-1}\omega_n^{n\cdot(ti)}}{n} =1=[n\mid k]$$
    继续阅读