离散对数（Discrete Logarithm）问题是这样一个问题，它是要求解模方程

$$a^x \equiv b \pmod m$$

这个问题是否存在多项式算法目前还是未知的，这篇文章先从 $m$ 是质数开始介绍大步小步法（Baby Step Giant Step）来解决它，之后再将其应用到 $m$ 是任意数的情况。这个算法可以在 $\mathcal O(\sqrt m)$ 的时间内计算出最小的 $x$，或者说明不存在这样一个 $x$

题目链接：BZOJ-2480、SPOJ-MOD、BZOJ-3239

(more…)

Read More

题目给出一个 $n$ 个点，$m$ 条边的有向图，要求求出删掉一些边以后，整个图强联通的方案数，其中 $n \leq 15, m \leq n(n-1)$

样例是这样的，十分良心，一共有 $9390$ 种方案

题目链接：BZOJ-3812

(more…)

Read More