#4275
摆动序列
摆动序列
题目描述
给定 k,统计满足以下条件的序列:
- 每个数均为 1 到 k 的整数。
- 序列至少含两个数。
- 序列中的数两两不同。
- 对第 3 项及以后:如果 ai−1 > ai−2,则 ai < ai−2;如果 ai−1 < ai−2,则 ai > ai−2。
条件比较的是新项与前两项中的较早一项 ai−2。例如 k=3 时,合法序列如下:
1 2
1 3
2 1
2 1 3
2 3
2 3 1
3 1
3 2
输入格式
一行一个整数 k,1 ≤ k ≤ 20。
输出格式
输出合法序列总数。
样例
3
8
1
0