p356.ans1
======================
1/6

=================
p356.in1
======================
2 5

=================
p356.ans2
======================
0

=================
p356.in2
======================
9 10

=================
statement.txt
======================
356. Extrasensory Perception
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



His Royal Highness the King of Berland Berl XV has just decapitated his magician for being politically incorrect. It is a truth universally acknowledged that every king in the possession of a good fortune is in a want of a decent sorcerer. Heralds all over the country have spread the news about the coming Berland-wide wizard competition that is to end up with the announcement of the winner's name. The winner is to join the royal retinue as His Royal Highness' Counselor.

Magician Resool graduated from Bexford University ten years ago and since that time he has been chased by misfortunes and disasters. His wife, an accomplished, still pretty looking lady, believes her husband can do much better than just grumbling about the unfair life. She suggests that he should try his magic powers at the competition and reminds him of his famous trick. The gist of the trick is to see through people's souls.

After two weeks of training Resool makes himself enter the Great Hall of Berland Palace and demonstrate his exceptional abilities. His Royal Highness the King of Berland Berl XV gives him an assignment: N men and N women are presented, and the fact is known that they form N married couples; Resool is to identify a wife for every husband. After the magician casts a spell, burns some magic herbs, and performs ritual dance he still fails to answer correctly. He only manages to guess K married couples out of N. But The King is full of sympathy for the magician and can't just let the magician go away jobless and sorrowful. So, he hires him as a yard-keeper. Now Resool has a lot of free time on his new job and wants to calculate the chances he had at the competition. He wants to know the probability of guessing correctly exactly K married couples when given N men, N women, and a fact that they form N married couples. This will definitely help him during the competition next time.

Input
Input file contains two integers K and N (1 ≤ N ≤ 100; 0 ≤ K ≤ N) separated by a space.

Output
Print the required probability to the output file. If the answer is zero, simply print "0" (without quotes). Otherwise print the answer in a form of irreducible fraction "A/B" (without quotes), where A and B are positive integers without leading zeroes. See examples below for the format of output.

Example(s)
sample input
sample output
2 5
1/6

sample input
sample output
9 10
0

=================
p356.py
======================
from math import gcd, factorial


def derangements(m):
    """
    Count permutations of m elements with no fixed points.
    """
    if m == 0:
        return 1
    if m == 1:
        return 0
    d_prev2, d_prev1 = 1, 0  # D_0, D_1
    for i in range(2, m + 1):
        d_prev2, d_prev1 = d_prev1, (i - 1) * (d_prev1 + d_prev2)
    return d_prev1


def main():
    # Each matching can be classified by a permutation. Let the secret one
    # be denoted as 1, ..., n. We are interested in the number of permutations
    # p1, ..., pn that match with 1, ..., n in exactly k positions. This is a
    # derangements problem: choose k positions to be fixed points, then the
    # remaining n-k must form a derangement (permutation with no fixed points).
    # The count is C(n, k) * D_{n-k}, where D_m is the m-th derangement number.
    # The probability is C(n, k) * D_{n-k} / n! = D_{n-k} / (k! * (n-k)!).
    #
    # Derangements can be counted via inclusion-exclusion. Let A_i be the set of
    # permutations where i is a fixed point. We want n! - |A_1 U ... U A_n|.
    # By inclusion-exclusion:
    # |A_1 U ... U A_n| = C(n,1) * (n-1)! - C(n,2) * (n-2)! + C(n,3) * (n-3)! - ...
    # So D_n = n! - C(n,1) * (n-1)! + C(n,2) * (n-2)! - ...
    #        = sum_{i=0}^{n} (-1)^i * C(n,i) * (n-i)!
    #        = sum_{i=0}^{n} (-1)^i * n! / i!
    #        = n! * sum_{i=0}^{n} (-1)^i / i!
    #
    # Alternatively, the recurrence D_n = (n-1) * (D_{n-1} + D_{n-2}), with
    # D_0 = 1, D_1 = 0. This follows from considering where element 1 maps: if
    # 1 -> j, then either j -> 1 (giving D_{n-2} ways for the rest) or j maps to
    # something else, equivalent to a derangement of n-1 elements as j and 1 can be
    # treated like one element (D_{n-1} ways).

    k, n = map(int, input().split())
    m = n - k
    d = derangements(m)

    if d == 0:
        print(0)
        return

    numerator = d
    denominator = factorial(k) * factorial(m)

    g = gcd(numerator, denominator)
    numerator //= g
    denominator //= g

    print(f"{numerator}/{denominator}")


if __name__ == "__main__":
    main()

=================
