Sherlock Counts Ways
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Watson gives an array of colored balls to Sherlock. All balls are identical in shape and size and hence, two balls with same color are indistinguishable. He gives to Sherlock an integer K and wants Sherlock to choose a bundle of K balls from the array. Sherlock is intrigued by the problem and starts wondering in how many different ways he can choose K such balls. Two ways are different if for any color c, there are different count of balls with color c in two chosen bundles.
First line contains N and K followed by N integers in next line denoting A1, A2, ..., AN - colors of the balls.
Output the required answer modulo 13313 in one line.
- 1 ≤ K ≤ N ≤ 2*105
- 1 ≤ Ai ≤ 2*105
Input 1: 4 2 3 2 2 3 Output 1: 3 Input 2: 5 1 2 2 2 2 2 Output 2: 1
Three possible ways are:
- [2, 2]
- [3, 3]
- [2, 3]
Only possible way is .
|Tags||combinatorics, cook75, darkshadows, divide-and-conq, fft, medium-hard|
|Time Limit:||8 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.