Problem Statement
You are given four
You have a deck of cards. Each card has a suit and a number. There are n different suits and k different numbers. There is a single card for each distinct (suit, number) pair, for a total of n * k cards in your deck.
You would like to get at least three cards in your hand that have the same number. Initially, all the cards are in the deck, and thus there are zero cards in your hand. You then repeat the following process.
- Draw a cards uniformly at random from the deck, and put them into your hand. (The deck will always have at least a cards at this point).
- If your hand has at least 3 cards of the same number, you win and stop.
- Otherwise, while your hand contains more than b cards, choose a card from your hand and return it to the deck.
Each execution of the above sequence of steps takes one second.
You would like to know the expected value of the number of seconds you need to finish this game, given that you try to minimize the time needed (by choosing which cards to return in the third step). It is guaranteed this value exists for every possible input that satisfies the constraints.
Let M = 998244353. It can be shown that the exact expected value is a rational number. Let P and Q be relatively prime nonnegative integers such that the expected value is P/Q. It can be shown that Q and M are relatively prime. Compute and return the value (P * Q^(-1)) modulo M, where Q^(-1) is the inverse element to Q modulo M.
Definition
- Class:
- TradeForTriples
- Method:
- findExpectation
- Parameters:
- int, int, int, int
- Returns:
- int
- Method signature:
- int findExpectation(int n, int k, int a, int b)
- (be sure your method is public)
Constraints
- n will be between 3 and 50, inclusive.
- k will be between 1 and 50, inclusive.
- a will be at least 1.
- b will be at least 1.
- a+b will be between 3 and n*k, inclusive.
Examples
3
1
1
2
Returns: 3
In this case, we would draw cards one by one until we have all cards in our hand.
3
2
1
2
Returns: 798595489
We can split this into two cases: The first two cards we draw are the same (happens with probability 2/5). It is optimal to wait until we draw the third card, and this takes 4 additional steps in expecation. The first two cards we draw are different (happens with probability 3/5). After drawing our third card, we get back to the first case, so this takes 5 additional steps in expectation. Thus, the answer is 2 + (4 * 2/5 + 5 * 3/5) = 33/5.
39
13
5
9
Returns: 873239918
29
12
5
9
Returns: 691554814
50
50
99
75
Returns: 923403294
50
50
2
1
Returns: 873466464
34
41
8
26
Returns: 783725367
12
45
5
4
Returns: 843166977
25
25
3
29
Returns: 704602220
29
13
3
6
Returns: 602266741
23
45
11
1
Returns: 708410296
3
17
3
1
Returns: 307
31
16
6
52
Returns: 838328365
20
13
5
2
Returns: 387936053
4
6
4
1
Returns: 665496245
37
42
64
8
Returns: 73367163
16
29
18
11
Returns: 933039575
44
47
11
16
Returns: 187652483
20
6
25
6
Returns: 1
10
42
8
1
Returns: 341652914
31
33
19
2
Returns: 266598652
11
50
2
11
Returns: 639983831
49
26
19
54
Returns: 885233826
42
23
12
5
Returns: 529009484
7
12
4
3
Returns: 505922554
43
47
23
16
Returns: 266216278
12
47
6
6
Returns: 343193880
24
17
5
15
Returns: 969035874
3
40
2
2
Returns: 417726536
44
28
77
1
Returns: 1
15
36
2
9
Returns: 663901315
29
31
24
21
Returns: 477011915
5
48
4
1
Returns: 1927370
3
18
3
2
Returns: 113620925
36
4
7
30
Returns: 162858203
39
45
15
8
Returns: 170171641
46
19
30
23
Returns: 53265091
32
24
31
3
Returns: 194014824
5
33
1
8
Returns: 967334817
8
10
6
8
Returns: 492254851
17
35
1
5
Returns: 597869634
33
23
4
10
Returns: 213504506
50
50
2499
1
Returns: 1
49
49
1400
1001
Returns: 1
50
50
49
48
Returns: 772532525