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

一道有趣的题目

其实是今天考试题,话说昨天做了 FWT 题今天就考一道 FWT 题真巧

题意

给出 $n$ 堆石子,每堆石子个数为 $a_i$ ,然后删掉几堆石子(不能全删),问至少删多少堆使后手必胜

题解

设 $XOR$ 为所有 $a_i$ 的异或和,则题目可以转化为选最少的数是它们异或起来为 $XOR$
继续阅读

BZOJ4589 Hard Nim

题目链接

题意

有 $n$ 堆石子,每堆石子个数是小于等于 $m$ 的质数,现在对这些石子玩 Nim 游戏,问后手必胜的方案数
$1\leq n \leq 10^9 , 2\leq m \leq 50000 $

题解

一道 $FWT$ 模板题
设 $F_n$ 表示考虑前 $n$ 堆石子,每堆石子数目异或值对应的生成函数,则
$$ F_n(i)=\sum_{j\oplus k = i} F_{n-1}(j) \cdot F_1(k) $$
继续阅读

快速沃尔什变换备忘录

这真的仅仅是一个备忘录,没什么自己的东西
包含一些莫比乌斯变换的东西
我一开始就到 picks 的博客上去学果然是个错误的决定,表示学完之后云里雾里
然后又找了几个博客,还是不太明白,果然是因为我太渣了
然后到学长的博客上去看了一下,真是好明白多了
既然别人有写得很仔细的文章了,我就懒得写了,可以到底下链接去看,我只会写一些我学习时遇到的一点问题
继续阅读

伯努利数备忘录

本文有将近 50 个公式,谨慎观看

定义及推导

定义伯努利数为满足
$$ \frac{x}{e^x-1}=\sum_{n\geq 0} B_n\frac{x^n}{n!} $$
的有理数列
虽然已经得到了它的生成函数,但是发现仅凭这样一个多项式并不好推
于是考虑将其化简,对 $e^x$ 泰勒展开后
$$ \frac{x}{e^x-1} = \frac{x}{\sum_{i\geq 0}\frac{x^i}{i!}-1} $$
$$\frac{x}{e^x-1}=\frac{x}{\sum_{i\geq 1}\frac{x^i}{i!}}​$$
继续阅读

多项式的一些奇怪操作

之前讲了一些多项式常用的操作

多项式除法与取模

对于一个 $n$ 次多项式 $A(x)$ 和一个 $m$次多项式 $B(x)$. $m\leq n$ .
求 $Q(x),R(x)$ 使
$$ A(x)\equiv Q(x)* B(x)+R(x) $$
其中 $Q(x)$ 是一个 $n-m$ 次多项式,而 $R(x)$ 是一个小于 $m$ 次的多项式
可以在 $O(n\log n)$ 复杂度内求出,求解思路清奇,一般记结论就行了。
记 $A^{r(n)}(x)$ 表示一个次数小于等于 $n$ 的多项式 $A(x)$ 以 $x^n$ 为最高次项进行翻转得到的多项式
显然 $A^{r(n)}(x)=x^n*A(\frac{1}{x})$
继续阅读

多项式备忘录

最近学了多项式相关的一些东西,写一点备忘录,主要是公式和证明,可能每次只会写一点点。

导数

部分简单函数的导数

$$ (e^x)’ = e^x , (\ln x)’=\frac{1}{x} , (\sin x)’ = \cos x , (\cos x)’ = -\sin x $$

函数复合求导

$$ (f(x)+g(x))’ = f'(x) + g'(x) $$
$$ (f(x)g(x))’ = f'(x)g(x)+f(x)g'(x) $$
$$ (f(g(x)))’ = f'(g(x))g'(x) $$
上面这个比较重要,经常容易忘记多个函数复合,都要求导。
继续阅读