P1044 [NOIP 2003 Junior] Stack

栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。 栈有两种最重要的操作，即 pop（从栈顶弹出一个元素）和 push（将一个元素进栈）。 栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。

 Ningning considers the following problem: given an operand sequence $1, 2, \ldots, n$ (the figure illustrates the case for $1$ to $3$), stack A has depth greater than $n$. Two operations are allowed: 1. Move a number from the head of the operand sequence to the top of the stack (corresponding to the stack push operation). 2. Move a number from the top of the stack to the end of the output sequence (corresponding to the stack pop operation). Using these two operations, one operand sequence can produce a set of output sequences. The following figure shows the process of generating the sequence `2 3 1` from `1 2 3`.  (The initial state is as shown above.) For a given $n$, your program should compute and output the total number of output sequences that can be obtained from the operand sequence $1, 2, \ldots, n$ through these operations.

The input contains a single integer $n$ ($1 \leq n \leq 18$).

Output a single line containing the total number of possible output sequences.

Source: NOIP 2003 Junior, Problem 3. Translated by ChatGPT 5