Skip to content

Instantly share code, notes, and snippets.

@xennygrimmato

xennygrimmato/russian_dolls_ways.py

Last active March 15, 2018 03:20
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save xennygrimmato/99be56ca69bb8d7f17bb05acae71af32 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save xennygrimmato/99be56ca69bb8d7f17bb05acae71af32 to your computer and use it in GitHub Desktop.
Download ZIP
CSAcademy - #73 - Russian Dolls Ways
Raw
russian_dolls_ways.py
from collections import Counter
MOD, N = 10**9 + 7, 10**5 + 2
fact = [1] + [j for j in [1] for i in xrange(1, N) for j in [(j * i) % MOD]]
inv = [pow(fact[i], MOD - 2, MOD) for i in xrange(N)]
def C(h, k): return (fact[h] * inv[k] * inv[h - k]) % MOD
n, d = raw_input(), Counter(map(int, raw_input().split())).most_common()
print (reduce(lambda x, y: (x * C(d[0][1], y[1]) * fact[y[1]]) % MOD, d, 1) * inv[d[0][1]]) % MOD
@pranet

pranet commented Mar 14, 2018 •
edited
Loading

Copy link
Copy Markdown

https://gist.github.com/pranet/4f6f1c7b9da82a0175f4a11d0ea155ce
Where is your god now? :P

@xennygrimmato

xennygrimmato commented Mar 15, 2018

Copy link
Copy Markdown
Author

https://gist.github.com/xennygrimmato/7df391c292f4068cd3bc4496cfe65826
Where is your god now? :D

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment