#P1870. 「Counting Swaps」 计数交换
「Counting Swaps」 计数交换
给定一个 1~n 的排列 ,可进行若干次操作,每次选择两个整数 x,y,交换 。
设把 变成单调递增的排列 1,2,…,n 至少需要 m 次交换。
求有多少种操作方法可以只用 m 次交换达到上述目标。
因为结果可能很大,你只需要输出结果对 取模之后的值。
例如排列 2,3,1 至少需要2次交换才能变为 1,2,3。操作方法共有3种,分别是:
方法一:先交换数字2,3,变成 3,2,1,再交换数字3,1,变成 1,2,3。
方法二:先交换数字2,1,变成 1,3,2,再交换数字3,2,变成 1,2,3。
方法三:先交换数字3,1,变成 2,1,3,再交换数字2,1,变成 1,2,3。
输入格式
第一行包含整数T,表示一共有T组测试用例。
每个测试用例前都会有一个空行。
每个测试用例包含两行,第一行包含整数n。
第二行包含n个整数,表示序列。
输出格式
每个测试用例输出一个结果,每个结果占一行。
数据范围
输入样例:
3
3
2 3 1
4
2 1 4 3
2
1 2
输出样例:
3
2
1
来源
- 《算法竞赛进阶指南》
- acwing 可能含有视频讲解