#P9832. Data Generation
Data Generation
Data Generation
Problem Description
Yoshinow2001 is making data for his problem. He wants to generate a random permutation of , so he used the following algorithm:
ans = 0
for i = 0, ..., n-1: a[i] = i
repeat m times:
choose i and j independently and uniformly from 0, ..., n-1
swap(a[i], a[j])
for i = 0, ..., n-1:
if a[i] != i: ans = ans + 1
The two indices may be equal. All draws are independent.
Original algorithm diagram Now Yoshinow2001 is concerned that this algorithm is not random enough ------ after all, if you want to randomize a permutation, the expected number of elements for should be . So he wants to ask what the mathematical expectation of the final is.
Input
The first line of input is a positive integer representing the number of data cases. For each cases consists of a single line of two integers , separated by a space. Where ,, ensure that is not a multiple of .
Output
For each test case, print one integer in representing the expected value of modulo . If the expectation is in lowest terms, print .
Sample Input
3
1 0
1 1
2 1
Sample Output
0
0
1
Source
2023“钉耙编程”中国大学生算法设计超级联赛(4)