Mock CCC '19 Contest 1 J5 - Pusheen Designs a Sushi Boat

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 0.6s
Memory limit: 1G

Problem type

Pusheen has been seeing a lot of sushi in her life lately and has taken to designing a sushi boat! She has N pieces of sashimi prepared and wants to select exactly K of them to put on her sushi boat. To maximize how pleasant her sushi boat looks, she refuses to put two pieces of sashimi on the boat if they come from the same fish.

How many different sushi boats can Pusheen construct? Two boats are different if Pusheen selects one piece of sashimi in one boat but does not select it in the other. Note that multiple pieces of sashimi can come from the same fish!


1 \le K \le N \le 10^3

1 \le f_i \le N

In tests worth 2 marks, K = 1.

In tests worth an additional 3 marks, K \le 2.

Input Specification

The first line contains two space-separated positive integers, N and K.

The next line contains N space-separated integers. Integer i on the line corresponds to f_i and indicates that piece i of sashimi came from fish f_i.

Output Specification

Output the number of distinct sushi boats that Pusheen can come up with, modulo 998\,244\,353.

Sample Input

4 3
1 2 2 3

Sample Output


Sample Explanation

Pusheen must select the 1st and 4th pieces of sashimi, but can choose either the 2nd or 3rd piece. This gives the two boats that Pusheen can construct.


  • 0
    MarksonChen  commented on May 10, 2021, 5:12 a.m. edit 3

    I'm stuck on #23 in the 3rd subtask... I get [218,197,204,191,190] and K = 5 as the values for this question, so isn't the answer 218 x 197 x 204 x 191 x 190 = 317936109360?

    • 1
      SuperClash  commented on May 10, 2021, 1:29 p.m.

      Output the number of distinct sushi boats that Pusheen can come up, modulo 998244353