#P10147. [2017备战wc]Arrangement
[2017备战wc]Arrangement
Arrangement
题目描述
为便于文字表达,将原题用两个人像表示的两种性质分别记为 性质 A 和 性质 B。
称长度为 的序列 具有性质 A,当且仅当
$$\forall i\in[1,s],\qquad\lvert a_i-a_{(i\bmod s)+1}\rvert=1.$$也就是说,相邻元素以及首尾元素的差的绝对值都为 。
称序列 具有性质 B,当且仅当:
- 。
- ,且 。
- 将 的元素重排列,所得的不同线性序列中,具有性质 A 的序列数量不超过 。
给定 ,求具有性质 B 的序列数,对 取模。
两个序列仅在每个位置的元素都相同时才视为相同;循环移位或反转后如果逐项不同,就分别计数。例如 和 是两个不同序列。单元素序列不具有性质 A,因此即使 ,它们仍具有性质 B。
输入格式
输入一行三个整数 。
输出格式
输出一行一个整数,表示答案。
数据范围
- 的数据满足 。
- 另有 的数据满足 。
- 另有 的数据满足 。
- 的数据满足 。
- 全部数据满足 ,。
样例1
输入:
2 1 0
输出:
2
合法的非递减序列为 、,两者均没有具有性质 A 的重排列。
样例2
输入:
2 2 2
输出:
5