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

莫比乌斯反演-例题

由于之前那篇备忘录要是再加上例题就太长了,所以单独开了一篇
可以先看一下前一篇文章
下文中默认 $n<m$

一个常见的套路

求 $n$ 以内和 $m$ 以内互质数对个数
$$
\begin{eqnarray}
&&\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1]\\
&=&\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)}\mu(d) \\
&=&\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d=1}^{n}\mu(d)\times [d\mid gcd(i,j)] \\
&=&\sum_{d=1}^{n}\mu(d)\sum_{i=1}^{n}\sum_{j=1}^{m}[d\mid gcd(i, j)] \\
&=&\sum_{d=1}^{n}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[1\mid gcd(i,j)]\\
&=&\sum_{d=1}^{n}\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor
\end{eqnarray}
$$
继续阅读

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