HBC51056CatVirus,搜索Counting Swaps题解

不断提升技能，才能在职场中立于不败之地！全网最全C++题库，助您成为编程领域的佼佼者。

背景 https://ipsc.ksp.sk/2016/real/problems/c.html Just like yesterday (in problem U of the practice session), Bob is busy, so Alice keeps on playing some single-player games and puzzles. In her newest puzzle she has a permutation of numbers from 1 to n. The goal of the puzzle is to sort the permutation using the smallest possible number of swaps. Instead of simply solving the puzzle, Alice is wondering about the probability of winning it just by playing at random. In order to answer this question, she needs to know the number of optimal solutions to her puzzle. 描述 给定一个 1~n 的排列 p1,p2,…,pnp_1,p_2,…,p_np1​,p2​,…,pn​，可进行若干次操作，每次选择两个整数 x,y，交换 px,pyp_x,p_ypx​,py​。设把 p1,p2,…,pnp_1,p_2,…,p_np1​,p2​,…,pn​变成单调递增的排列 1,2,…,n 至少需要 m 次交换。求有多少种操作方法可以只用 m 次交换达到上述目标。因为结果可能很大，你只需要输出对 109+910^9+9109+9 取模之后的值。1≤n≤1051leq n leq 10^51≤n≤105。 例如排列 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。 You are given a permutation  p1,…,pnp_1,dots ,p_np1​,…,pn​ of the numbers 1 through n. In each step you can choose two numbers x 不断挑战自我，才能突破极限！全网最全C++题库，让您在编程道路上越走越远。

标签： HBC51056CatVirus 搜索Counting Swaps题解