约瑟夫环

经典问题,n个人编号0~n-1,从0开始每m个人出去一个,求最后一个出环的人。

  • 链表的解法复杂度为O(nm)

  • 递推法,设$f_n$为最后留下的人的编号$f_n=(f_{n-1}+m) \mod n$ 复杂度O(n)

  • 第k个死亡的人编号 复杂度 O(log(n))

    1
    2
    3
    4
    5
    6
    int kth(int n, int m, int k)
    {
    if (m == 1) return n-1;
    for (k = k*m+m-1; k >= n; k = k-n+(k-n)/(m-1));
    return k;
    }
  • 参考

Fibonacci/Catalan

类似于Fibonacci 和 Catalan 数的当前状态是前驱状态的累加/累乘等等。

构造矩阵

$
\text{对于递推式} f_{n+1} = af_{n} + bf_{n-1} \\
\text{我们有如下构造} \\
$

$\begin{bmatrix} f_{n+1} \\ f_{n} \end{bmatrix} = \begin{bmatrix} a & b \\ 1 & 0 \end{bmatrix} \begin{bmatrix} f_{n} \\f_{n-1} \end{bmatrix}$

$\left[ \begin{matrix} f_{n} \\ f_{n-1} \end{matrix} \right] = \left[ \begin{matrix} a & b \\ 1 & 0 \end{matrix} \right]^{n-2} \left[ \begin{matrix} f_2 \\ f_1 \end{matrix} \right]$

然后递推可以以矩阵快速幂求解(注意n>2)