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

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

BZOJ4911 切树游戏

建议在 LOJ 上提交

题解

一开始想用点分治然后DP,结果发现会统计不合法答案,后来去看题解了,发现这题简直神题
算法:动态dp+FWT
虽然题目中表示树是无根的,但是我们还是可以随便选一个点作为根
设 $f(i,k)$ 为以 $i$ 为根节点的子树,异或值为 $k$ 的联通子树个数
发现某个节点的 $f$ 值可以从所有子树的 $f$ 做异或卷积转移得来
具体地说,设 $F_i(z)$ 代表 $i$ 的 $f$ 数组的生成函数,则
$$ F_i(z) = z^{v_i} \prod (F_{son_i}(z)+z^0)$$
其中卷积为异或卷积
继续阅读

BZOJ5153 州区划分

bzoj上不能测试这题,需要下载数据手动测试,我写了个linux上的简易测试脚本
下载本地测试文件,将自己的程序重命名为 5153.cpp 放进解压后的文件夹里,然后把从 bzoj 上下载的数据也放进去,输入 sh test.sh 等待结果就行
update: 后来发现 UOJ 上也有

题面

链接

题解

设 $f _ S$ 为点集为 $S$ 时的答案,$g _ S$ 为点集为 $S$ 且点集对应的图合法时集合中所有点的权值和,$sum _ S$ 为点集 $S$ 中所有点的权值和
显然,当 $S$ 合法时 $g _ S=sum _ S$ ,否则 $g _ S=0$
根据题目
$$ f _ S=\sum _ {T\subseteq S} f _ {S-T}\times \big{(}\frac{g _ T}{sum _ S}\big{)}^p $$
继续阅读

BZOJ4036 按位或

vfk 论文上的一道例题

题意

给出 $n$ ,每秒会有 $p_i$ 的概率选择 $i ,i \in [0, 2^n – 1]$ ,与手上的数进行异或,问期望多少次后手上的数会变成 $2^n-1$

题解

果然还是应该用 $\hat f$ 来表示 $f$ 的莫比乌斯变换,不然我整个人都比较懵
设 $f_i$ 表示操作 $i$ 次后得到数字的概率的生成函数, $U$ 为 $2^n – 1$
设 $h_S$ 表示得到 $S$ 的期望操作次数,将 $f$ 看成集合幂级数,则
$$ h_S = \sum_{k=1}^{\infty} k\cdot(f^k – f^{k-1}) $$
继续阅读