2023年全國青少年信息素養大賽C++編程初中組決賽真題+答案解析

編程題

---

第一題 判斷是否存在重復的子序列

題目描述
從m 個字符中選取字符,生成n 個符號的序列,使得其中沒有2 個相鄰的子序列相同? 如從1,2,3,生成長度為5 的序列,序列“12321”是合格的,而“12323”和“12123” 是不合格?問:已知m 和n 都是小于等于10 的數字,求m 個不同字符,組成長度n 的序列 中,無2 個相鄰相同的子序列的序列總數?

輸入格式
一行兩個正整數,第一個是m,表示不同的字符,第二個是n,表示序列長度,0<m<=n<=10? (0<m<=n<=10) 。

輸出格式
一個數,表示序列種沒有2 個相鄰相同的子序列的序列總數?

樣例輸入
3 5

樣例輸出
30

---

題目解析
本題要計算由m個不同字符組成的長度為n的序列中，不存在兩個相鄰相同子序列的序列總數。這里的“相鄰子序列”指長度為2的相鄰子序列，即對于序列中任意位置i（1≤i<n-1）&