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）&