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$ 个 继续阅读

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}$
这里只是简要讲解,更详细的请到引用资料里看
继续阅读