对顶数据结构

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

HDU4699
HDU4699

具体数学:递归模型

Hanoi塔

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

Tn=2Tn1+1T_n = 2T_{n-1} + 1

  • Hanoi 塔扩展模型(一)

    • 2n2n 个圆盘,nn 种不同的尺寸,每种尺寸圆盘恰有22
      相同尺寸圆盘不区分

    • 问题求解并不复杂,将圆盘分组,一组是相同尺寸的22 个,一共有nn
      AnA_n 为操作第nn 圆盘所需要的移动次数

    An=2An1+2A_n = 2A_{n-1} + 2

    1. 将前面的n1n-1 组移到tmp\text{tmp} 这个辅助柱子上,耗费An1A_{n-1}
    2. 将底层的22 个圆盘移动到目标柱子上,耗费22 次,注意这里更改了编号顺序
    3. n1n-1 组移动到目标柱子上
    • 实际上
      这里的目标状态为 前n1n-1 个盘顺序不变,最后一组的22 个盘顺序相反
  • Hanoi 塔扩展模型(二)—— 要求移动后的顺序和原来的一致
    hanoi-01
    hanoi-02

  • Hanoi 塔扩展模型 (三)

    • 圆盘具有nn 种不同的尺寸,恰好有mkm_k 个圆盘尺寸是kk
    • 如果无所谓相同尺寸的顺序

      A(m1mn)=2A(m1mn1)+mn=2n1m1+2n2m2+20mn\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. mn=1m_n=1,即尺寸为nn 的圆盘只有一种

        B(m1mn)=2A(m1mn1)+1=A(m1mn)(mn=1)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=1n = 1,此时只有11 种尺寸,问题转换为求解kk同一尺寸的圆盘移动所需代价
        最后留下最底下的11 个圆盘,然后整体移动上面的mn1m_n-1 个圆盘

        B(m1mn)=2(mn1)+1=2mn1B(m_1\cdots m_n) = 2(m_n-1) + 1 = 2m_n - 1

      3. n>1n > 1 andmn>1m_n > 1

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

  • Hanoi 塔扩展模型(四)—— 四根柱子的塔

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

      1. 将上面的nkn-k 个盘子移动到第四根空柱子,代价为WnkW_{n-k}
      2. 将剩下的kk 个柱子,转换成为三根柱子的标准 Hanoi 塔模型
        移动的代价为TkT_k
      3. 将第四根柱子的所有盘子,移动到目标柱子,代价仍为WnkW_{n-k}
    • 综上所述

      Wn=2Wnk+Tk(0kn)W_n = 2W_{n-k} + T_k \quad (0 \leqslant k \leqslant n)

直线分割模型

平面上的nn 条直线所界定的区域的最大个数LnL_n
即最多能把平面分割成几部分?
line

  • 直线分割模型拓展(一)—— 任意直线线段组合图形,比如ZZ 字形

    Zn=Zn1+p(n1)+1Z_n = Z_{n-1} + p\cdot (n-1) + 1

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

    如果是VV 字形,此时p=4p = 4,因为两个VV 字形最多产生44 个交点

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

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

    Pn=Pn1+Ln1P_n = P_{n-1} + L_{n-1}

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

约瑟夫问题

{J(1)=1J(2n)=2J(n)1n1J(2n+1)=2J(n)+1n1\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=2m+ln = 2^m + l

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

    • 注意到如果2mn<2m+12^m \leqslant n < 2^{m+1},实际上l=nmod2ml = n \bmod 2^m0l<2m0 \leqslant l < 2^m
  • 循环移位
    如果将nn 写成二进制形式,n=(bmbm1b1b0)2, l=nmod2mn = (b_mb_{m-1}\cdots b_1b_0)_2, \ l = n \bmod 2^m

    l=(bm1bm2b1b0)22l=(bm1bm2b1b00)22l+1=(bm1bm2b1b01)2,bm=1J(n)=2l+1=(bm1bm2b1b0bm)2\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)J(n) 作用于nn,实际上是相当于将nn 的二进制环形循环左移11
    如果遇到前导00 则扔掉,如此执行若干次

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

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

成套方法

成套方法简介

递归式

f(1)=αf(2n)=2f(n)+βn1f(2n+1)=2f(n)+γn1\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)α+B(n)β+C(n)γf(n) = A(n)\alpha + B(n)\beta +C(n) \gamma

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

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

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

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

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

成套方法步骤

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

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

    1=α1=2+ββ=11=2+γγ=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)=1A(n)-B(n)-C(n) = f(n)=1

  • f(n)=nf(n) = n 不动点

    1=α2n=2n+ββ=02n+1=2n+γγ=1\begin{gathered} 1 = \alpha \\ 2n = 2n + \beta && \Rightarrow \beta = 0 \\ 2n+1 = 2n + \gamma && \Rightarrow \gamma = 1 \end{gathered}

    由此,可以推出
    A(n)+C(n)=nA(n)+C(n) = n

  • 综上所述

    A(n)=2mn=2m+l and 0l<2mA(n)B(n)C(n)=1A(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}

递归式与基变换

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

f(j)=aj1j<df(dn+j)=cf(n)+βj0j<d, n1\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((bmbm1b1b0)d)=(αbmβbm1βbm2βb1βb0)cf\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

例如给定递归式

f(1)=34f(2)=5f(3n)=10f(n)+76n1f(3n+1)=10f(n)2n1f(3n+2)=10f(n)+8n1\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)f(19),注意到19=(201)319 = (201)_3

f(19)=f((201)3)=(α2 β0 β1)10=(5 76 2)10=1258\begin{gathered} f(19) = f((201)_3) = (\alpha_2 \ \beta_0 \ \beta_1)_{10} \\ = (5 \ 76 \ -2)_{10} = 1258 \end{gathered}

约瑟夫问题扩展

任意位置

UVALive3882
UVALive3882

约瑟夫问题推广

josephus-01

Josephus问题的一些结论

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

先来看 Josephus 方程的递推形式

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

其中,f(n)f(n) 表示当前有nn 个人
从初始位置00 开始 (00 位置不删除)
最后幸存者的编号是f(n)f(n)
josephus-02

特殊计数序列——Catalan数

定理 考虑由nn+1+1nn1-1 组成的2n2n 项序列

a1,a2,,a2na_1, a_2, \cdots , a_{2n}

其部分和总是满足

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

这种序列的个数等于第nn 个 Catalan 数

Cn=1n+1(2nn)(n0)C_n = \frac{1}{n+1} {2n \choose n} (n \geqslant 0)

证明如下
Catalan

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

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

从而

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

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

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

阶乘分解

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

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

试除法分解质因数

1
2
3
4
5
6
7
8
9
10
11
12
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
}

朴素筛法求质数

1
2
3
4
5
6
7
8
9
10
11
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;
}
}

线性筛法求质数

primes

1
2
3
4
5
6
7
8
9
10
11
12
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 数

1n+1(2nn)\frac{1}{n+1} {2n \choose n}

algorithm

  • 打表[2,2n][2, 2n] 所有的素数
  • 阶乘分解,for pprimes[]\bold{for} \ \forall p \in \bold{primes}[\cdots]
    求出pw[p]=get(2n,p)2get(n,p)\bold{pw}[p]= \bold{get}(2n, p) - 2\cdot \bold{get}(n, p)
    即素数pp(2nn)2n \choose n 这项中的幂指
  • n+1n+1 进行素因子分解,n+1=psn+1 = \cdots p^s \cdots,然后pw[p]=s\bold{pw}[p] -= s
  • for pprimes[]:\bold{for} \ \forall p \in \bold{primes}[\cdots]: 执行pw[p]\bold{pw}[p]muti(ans,p)\bold{muti}(ans, p)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
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);
}