Sorting Permutations

题意翻译

问题描述：我们有一个是1到n 的排列的序列a1, a2,... ,an。在一秒钟里，我们可以选择一些不相交的数对(u1，v1)，(u2，v2)，... (uk，vk)并交换所有a_ui 和a_vi，同时对于所有的i 有1<=ui < vi<=n。数对们不相交当且仅当所有的ui 和vi 不相同。 我们想要尽快地把序列重新排列成递增顺序。给定初始排列，计算完成排序的方法数。两种方法不同当且仅当有一个时间t，此时用于交换的数对集合不相同（数对的顺序不重要）。如果给定的排列已经排好序，那么排序所需时间为零，排序方法唯一。 为了让这个问题更有趣，我们在排列上打k个洞。因此，在a1,a2,...,an 中恰好有k个数没有被确定。对于填充这些洞的所有可能情况，计算方法数，然后输出这些值的和模1000000007（10^9 + 7）。 输入：第一行包含两个整数n（1<=n <=10^5）和k（0<=k<=12）。第二行为排列序列a1,...,an（0<=ai<=n）。如果一个数没有被确定，那么它被标记为0。序列有恰好k个0。对于其他不等于零的ai 来说，它们之间两两不相同。 输出：方法数之和模1000000007（10^9 + 7）。

题目描述

We are given a permutation sequence $ a_{1},a_{2},...,a_{n} $ of numbers from $ 1 $ to $ n $ . Let's assume that in one second, we can choose some disjoint pairs $ (u_{1},v_{1}),(u_{2},v_{2}),...,(u_{k},v_{k}) $ and swap all $ a_{ui} $ and $ a_{vi} $ for every $ i $ at the same time ( $ 1<=u_{i}&lt;v_{i}<=n $ ). The pairs are disjoint if every $ u_{i} $ and $ v_{j} $ are different from each other. We want to sort the sequence completely in increasing order as fast as possible. Given the initial permutation, calculate the number of ways to achieve this. Two ways are different if and only if there is a time $ t $ , such that the set of pairs used for swapping at that time are different as sets (so ordering of pairs doesn't matter). If the given permutation is already sorted, it takes no time to sort, so the number of ways to sort it is $ 1 $ . To make the problem more interesting, we have $ k $ holes inside the permutation. So exactly $ k $ numbers of $ a_{1},a_{2},...,a_{n} $ are not yet determined. For every possibility of filling the holes, calculate the number of ways, and print the total sum of these values modulo $ 1000000007 $ $ (10^{9}+7) $ .

输入输出格式

输入格式

The first line contains two integers $ n $ $ (1<=n<=10^{5}) $ and $ k $ $ (0<=k<=12) $ . The second line contains the permutation sequence $ a_{1},...,a_{n} $ $ (0<=a_{i}<=n) $ . If a number is not yet determined, it is denoted as $ 0 $ . There are exactly $ k $ zeroes. All the numbers $ a_{i} $ that aren't equal to zero are distinct.

输出格式

Print the total sum of the number of ways modulo $ 1000000007 $ $ (10^{9}+7) $ .

输入输出样例

输入样例 #1

5 0
1 5 2 4 3

输出样例 #1

6

输入样例 #2

5 2
1 0 2 4 0

输出样例 #2

7