具体数学：递归模型与计数模型

对顶数据结构

始终在序列中间的某个指定位置进行操作
此类问题经常用对顶数据结构
对顶数据结构常用的有“对顶栈，对顶堆”

HDU4699

具体数学：递归模型

Hanoi塔

三根柱子的 Hanoi 塔模型的递归解为

$$T_n = 2T_{n-1} + 1$$

• Hanoi 塔扩展模型（一）

  • $2n$ 个圆盘，$n$ 种不同的尺寸，每种尺寸圆盘恰有 $2$ 个
    相同尺寸圆盘不区分

  • 问题求解并不复杂，将圆盘分组，一组是相同尺寸的 $2$ 个，一共有 $n$ 组
    记 $A_n$ 为操作第 $n$ 组圆盘所需要的移动次数

  $$A_n = 2A_{n-1} + 2$$

  1. 将前面的 $n-1$ 组移到 $\text{tmp}$ 这个辅助柱子上，耗费 $A_{n-1}$
  2. 将底层的 $2$ 个圆盘移动到目标柱子上，耗费 $2$ 次，注意这里更改了编号顺序
  3. 将 $n-1$ 组移动到目标柱子上
  • 实际上
    这里的目标状态为 前 $n-1$ 个盘顺序不变，最后一组的 $2$ 个盘顺序相反

• Hanoi 塔扩展模型（二）—— 要求移动后的顺序和原来的一致
  
  

• Hanoi 塔扩展模型 (三)

  • 圆盘具有 $n$ 种不同的尺寸，恰好有 $m_k$ 个圆盘尺寸是 $k$
  • 如果无所谓相同尺寸的顺序

    $$\begin{gathered} A(m_1\cdots m_n) = 2A(m_1\cdots m_{n-1}) + m_n \\ = 2^{n-1}m_1 + 2^{n-2}m_2 + \cdots 2^0m_n \end{gathered}$$

  • 如果需要考虑相同尺寸的顺序
    1. $m_n=1$，即尺寸为 $n$ 的圆盘只有一种

       $$B(m_1\cdots m_n) = 2A(m_1\cdots m_{n-1}) + 1 = A(m_1\cdots m_n) \quad (m_n=1)$$

    2. $n = 1$，此时只有 $1$ 种尺寸，问题转换为求解 $k$ 个同一尺寸的圆盘移动所需代价
       最后留下最底下的 $1$ 个圆盘，然后整体移动上面的 $m_n-1$ 个圆盘

       $$B(m_1\cdots m_n) = 2(m_n-1) + 1 = 2m_n - 1$$

    3. $n > 1$ and $m_n > 1$

       $$B(m_1\cdots m_n) = 2A(m_1\cdots m_{n-1}) + 2m_n + B(m_1\cdots m_{n-1})$$

• Hanoi 塔扩展模型（四）—— 四根柱子的塔

  • 不妨记四根 Hanoi 塔的移动代价为 $W_n$ (有 $n$ 个盘子)

    1. 将上面的 $n-k$ 个盘子移动到第四根空柱子，代价为 $W_{n-k}$
    2. 将剩下的 $k$ 个柱子，转换成为三根柱子的标准 Hanoi 塔模型
       移动的代价为 $T_k$
    3. 将第四根柱子的所有盘子，移动到目标柱子，代价仍为 $W_{n-k}$

  • 综上所述

    $$W_n = 2W_{n-k} + T_k \quad (0 \leqslant k \leqslant n)$$

直线分割模型

平面上的 $n$ 条直线所界定的区域的最大个数 $L_n$
即最多能把平面分割成几部分？

• 直线分割模型拓展（一）—— 任意直线线段组合图形，比如 $Z$ 字形

  $$Z_n = Z_{n-1} + p\cdot (n-1) + 1$$

  其中， $p$ 表示两个图形做多能够产生的交点数

  如果是 $V$ 字形，此时 $p = 4$，因为两个 $V$ 字形最多产生 $4$ 个交点

• 直线分割模型拓展 (二) —— 三维区域
  比如在一块厚奶酪上，划出 $k$ 道切痕，问最多能得到多少块奶酪
  

  • $P_n$ 表示 $n$ 个不同平面能够界定的三维区域最大个数

  $$P_n = P_{n-1} + L_{n-1}$$

  • 其中 $L_{n}$ 表示平面上的 $n$ 条直线能够界定的区域最大个数

约瑟夫问题

$$\begin{cases} J(1) = 1 \\ J(2n) = 2J(n) - 1 && n \geqslant 1 \\ J(2n+1) = 2J(n) + 1 && n \geqslant 1 \end{cases}$$

• 递归式的封闭形式 $n = 2^m + l$

  $$J(2^m+l) = 2l+1, \quad m \geqslant 0, \ 0 \leqslant l < 2^m$$

  • 注意到如果 $2^m \leqslant n < 2^{m+1}$，实际上 $l = n \bmod 2^m$，$0 \leqslant l < 2^m$

• 循环移位
  如果将 $n$ 写成二进制形式，$n = (b_mb_{m-1}\cdots b_1b_0)_2, \ l = n \bmod 2^m$

  $$\begin{gathered} l = (b_{m-1}b_{m-2}\cdots b_1b_0)_2 \\ 2l = (b_{m-1}b_{m-2}\cdots b_1b_00)_2 \\ 2l + 1 = (b_{m-1}b_{m-2}\cdots b_1b_01)_2 , \quad b_m = 1 \\ J(n) = 2l+1 = (b_{m-1}b_{m-2}\cdots b_1b_0b_m)_2 \end{gathered}$$

• $J(n)$ 作用于 $n$，实际上是相当于将 $n$ 的二进制环形循环左移 $1$ 位
  如果遇到前导 $0$ 则扔掉，如此执行若干次

  $$\begin{gathered} (J(J\cdots J(n) \cdots )) = 2^{V(n)} - 1 \\ V(n) \text{表示} n \text{中有几个为} 1 \text{的位} \end{gathered}$$

  • 特别地，如果有 $J(n) = n/2$，那么 $n$ 循环左移 $1$ 位（舍弃前导0）与循环右移 $1$ 位的结果相等

    n/2 = n >> 1
    J(n) = n 循环左移 1 位

成套方法

成套方法简介

递归式

$$\begin{gathered} f(1) = \alpha \\ f(2n) = 2f(n) + \beta && n \geqslant 1 \\ f(2n+1) = 2f(n) + \gamma && n \geqslant 1 \end{gathered}$$

根据枚举猜想，最后可以表示成形式

$$f(n) = A(n)\alpha + B(n)\beta +C(n) \gamma$$

如果令 $n = 2^m + l$，此时有 $0 \leqslant l < 2^m \ (n \geqslant 1)$

$$\begin{gathered} A(n) = 2^m \\ B(n) = 2^m - 1 - l \\ C(n) = l \end{gathered}$$

检验任意特殊值 $\alpha = 1, \beta = \gamma = 0, \Longrightarrow f(n) = A(n)$

$$\begin{gathered} A(1) = 1 \\ A(2n) = 2A(n) && n \geqslant 1 \\ A(2n+1) = 2A(n) && n \geqslant 1 \\ \end{gathered}$$

而上面猜想说 $A(n) = 2^m$ 是否正确？
$A\left(2^{m+1}+2 l\right) \Longrightarrow \text{对m归纳}, 0 \leqslant 2l < 2^{m+1}$
$A\left(2^{m+1}+2 l\right) = 2^{m+1}$
$A\left(2^{m+1}+2 l\right) = 2A(2^m + l) = 2\cdot 2^m = 2^{m+1}$
猜想正确

成套方法步骤

成套方法一般取特殊的函数值来求解

• 取 $f(n) = 1$ 常值函数

  $$\begin{gathered} 1 = \alpha \\ 1 = 2 + \beta && \Rightarrow \beta = -1 \\ 1 = 2 + \gamma && \Rightarrow \gamma = -1 \end{gathered}$$

  由此，可以推出
  $A(n)-B(n)-C(n) = f(n)=1$

• 取 $f(n) = n$ 不动点

  $$\begin{gathered} 1 = \alpha \\ 2n = 2n + \beta && \Rightarrow \beta = 0 \\ 2n+1 = 2n + \gamma && \Rightarrow \gamma = 1 \end{gathered}$$

  由此，可以推出
  $A(n)+C(n) = n$

• 综上所述

  $$\begin{gathered} A(n) = 2^m && n = 2^m+l \ \bold{and} \ 0 \leqslant l < 2^m \\ A(n)-B(n)-C(n) = 1 \\ A(n) + C(n) = n \end{gathered}$$

递归式与基变换

对递归式问题进行推广，对于递归式

$$\begin{gathered} f(j) = a_j && 1 \leqslant j < d \\ f(dn+j) = cf(n) + \beta_j && 0 \leqslant j < d, \ n \geqslant 1 \end{gathered}$$

根据基数与进制分解的原理，变动基数的解可以表示如下

$$f\left( (b_mb_{m-1}\cdots b_1b_0)_d \right) = (\alpha_{b_m} \beta_{b_{m-1}} \beta_{b_{m-2}} \cdots \beta_{b_1}\beta_{b_0})_c$$

例如给定递归式

$$\begin{gathered} f(1) = 34 \\ f(2) = 5 \\ f(3n) = 10f(n) + 76 && n \geqslant 1 \\ f(3n+1) = 10f(n)-2 && n \geqslant 1 \\ f(3n+2) = 10f(n)+8 && n \geqslant 1 \end{gathered}$$

计算 $f(19)$，注意到 $19 = (201)_3$

$$\begin{gathered} f(19) = f((201)_3) = (\alpha_2 \ \beta_0 \ \beta_1)_{10} \\ = (5 \ 76 \ -2)_{10} = 1258 \end{gathered}$$

约瑟夫问题扩展

任意位置

UVALive3882

约瑟夫问题推广

Josephus问题的一些结论

约瑟夫发现自己处在给定位置 $j$，并且他有一次机会来指定淘汰参数 $q$
使得每 $q-1$ 个人处死一人，问他能否保全自己

先来看 Josephus 方程的递推形式

$$\begin{gathered} f(1) = 0 \\ f(n) = (f(n-1) + q) \bmod n \end{gathered}$$

其中，$f(n)$ 表示当前有 $n$ 个人
从初始位置 $0$ 开始 ($0$ 位置不删除)
最后幸存者的编号是 $f(n)$

特殊计数序列——Catalan数

定理 考虑由 $n$ 个 $+1$ 和 $n$ 个 $-1$ 组成的 $2n$ 项序列

$$a_1, a_2, \cdots , a_{2n}$$

其部分和总是满足

$$a_1+a_2+\cdots + a_k \geqslant 0 \quad (\forall k = \{1, 2, \cdots, 2n \})$$

这种序列的个数等于第 $n$ 个 Catalan 数

$$C_n = \frac{1}{n+1} {2n \choose n} (n \geqslant 0)$$

证明如下

通过以上证明了任意不可接受序列 $U(n, n)$ 与序列 $C(n+1, n-1)$ 存在对应关系
$C(n+1, n-1)$ 的个数实际上就是排列数

$$\frac{(2n)!}{(n+1)!(n-1)!}$$

从而

$$U(n) = \frac{(2n)!}{(n+1)!(n-1)!}$$

$$A(n) = {2n \choose n} - U(n) = \frac{1}{n+1}{2n \choose n}$$

计数类问题编程实现常用函数

阶乘分解

对于 $N!$ 进行阶乘分解的结果是

$$\sum_{p^k \leqslant N} \lfloor \frac{N}{p_k} \rfloor$$

试除法分解质因数

void divide(int x) {
    for (int i = 2; i <= x/i; i++) {
        if (x % i == 0) {
            int s = 0;
            while (x % i == 0) s++, x /= i;
            // i^s
            make_pair(i, s);
        }
    }
    if (x > 1) make_pair(x, 1);
    // x^1
}

朴素筛法求质数

vector<int> primes;
bool st[maxn]; // init st[...] = 0
// st = true 表示这个数是合数

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (st[i]) continue;
        primes.push_back(i);
        for (int j = 2*i; j <= n; j += i) st[j] = true;
    }
}

线性筛法求质数

vector<int> primes;
bool st[maxn];

void get_primes() {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes.push_back(i);
        for (int j = 0; primes[j] <= n/i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j]) break;
        }
    }
}

Catalan 数经典应用

这里涉及到一个编程技巧，叫高精度压位
Acwing130

其实就是计算 Catalan 数

$$\frac{1}{n+1} {2n \choose n}$$

algorithm

• 打表 $[2, 2n]$ 所有的素数
• 阶乘分解，$\bold{for} \ \forall p \in \bold{primes}[\cdots]$
  求出 $\bold{pw}[p]= \bold{get}(2n, p) - 2\cdot \bold{get}(n, p)$
  即素数 $p$ 在$2n \choose n$ 这项中的幂指
• 对 $n+1$ 进行素因子分解，$n+1 = \cdots p^s \cdots$，然后 $\bold{pw}[p] -= s$
• $\bold{for} \ \forall p \in \bold{primes}[\cdots]:$ 执行 $\bold{pw}[p]$ 次 $\bold{muti}(ans, p)$

const int maxn = 120000 + 10;
int n;

vector<int> primes;
bool st[maxn];

void get_primes() {
    memset(st, 0, sizeof st);
    for (int i = 2; i <= 2*n; i++) {
        if (st[i]) continue;
        primes.push_back(i);
        for (int j = 2*i; j <= 2*n; j += i) st[j] = true;
    }
}

int pw[maxn];

inline int get(int n, int p) {
    int s = 0;
    while (n) s += n/p, n /= p;
    return s;
}

void multi(vector<ll>& res, int b) {
    ll t = 0;
    for (int i = 0; i < res.size(); i++) {
        t += res[i] * b;
        res[i] = t % 100000000, t /= 100000000;
    }
    while (t) res.push_back(t % 100000000), t /= 100000000;
}

void out(const vector<ll>& res) {
    printf("%lld", res.back());
    for (int i = res.size()-2; i >= 0; i--) {
        printf("%08lld", res[i]);
    }
    printf("\n");
}

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> n;

    // get primes
    get_primes();

    // divide factorial
    for (auto p : primes) pw[p] = get(2*n, p) - 2 * get(n, p);

    // divide
    int x = n+1;
    for (auto p : primes) if (p <= x) {
        int s = 0;
        while (x % p == 0) s++, x /= p;
        pw[p] -= s;
    }

    // multi
    vector<ll> ans;
    ans.push_back(1);
    for (auto p : primes) {
        for (int j = 0; j < pw[p]; j++) multi(ans, p);
    }

    // output
    out(ans);
}