请教一个有关随机数生成算法方面的算法问题,利用C语言算法的实现的过程方式

Problem Description
Teacher Mai has a game machine, which has n slots in a row, numbered from 1 to n, inclusively. He plays a game with the machine for several rounds. In each round, he divides that row into k segments with marks at boundaries between adjacent segments. Each segment must contain a positive number of slots. Then, the machine generates a random permutation of {1,2,⋯,n} and displays the permutation on the slots.Finally, the machine calculates the inversion number of each segment and multiplies them together to get the score of the round. The inversion number of a sequence is the number of inversions (also called inversion pairs) in the sequence.

Teacher Mai can play the game for as many rounds as he wants, but he must use different partitions in different rounds. Two partitions are considered to be different if there is a mark somewhere in one partition but not in the other. The total game score is simply the sum of the score of each round. However, the machine has been intruded by a malware, which changes the permutation before the machine calculates the score of each round. It sorts the numbers in the m specific slots with numbers p1,p2,⋯,pm.

For example, if n=4,k=1,m=2,p={1,3} and the permutation generated is (2,4,1,3). The malware will pick numbers 2 and 1 and sort them, changing the permutation into (1,4,2,3). So Teacher Mai will get a score of 2 (pairs (4,2) and (4,3)) in this round. Teacher Mai wants to know the maximum expected game score he can get.

Input
There are multiple test cases.

For each test case, the first line contains three numbers n,k,m(1≤k,m≤n≤100).

The second line contains m numbers p1,p2,⋯,pm(1≤p1<p2<⋯<pm≤n).

In the i-th test case, n=10i.

Output
As the answer for the problem can be very large, please calculate it as an irreducible fraction A/B and output (A∗B−1) mod (109+7) for each test case in a separate line. Here, B−1 is the multiplicative inverse of B modulo 109+7. The input constraints guarantee that B and 109+7 are coprime, so this expression is properly defined.

Sample Input
6 2 3
1 4 5
10 3 4
2 6 7 9

Sample Output
225000005
608333402

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐