diff options
Diffstat (limited to 'others/other/chonso.py')
-rwxr-xr-x | others/other/chonso.py | 98 |
1 files changed, 98 insertions, 0 deletions
diff --git a/others/other/chonso.py b/others/other/chonso.py new file mode 100755 index 0000000..e1e4da3 --- /dev/null +++ b/others/other/chonso.py @@ -0,0 +1,98 @@ +#!/usr/bin/env python3 +from fractions import Fraction +from functools import reduce +from math import factorial +from operator import floordiv, mul + + +class Polynomial: + """A fixed-length power series class. + + The Polynomial class is made to calculate the number of permutations + and combinations using generating function, so it only provides '+', + '*', '**' methods and doesn't support negative power degrees. + + Parameters + ---------- + coef : iterable of numeric objects + Polynomial coefficients in order of increasing degree, i.e., + ``(1, 2, 3)`` give ``1 + 2*x + 3*x**2``. + + length : int + Maximum length for coef + """ + MAXLEN = 1001 + + def __init__(self, coef, length=None): + self.coef = list(coef)[:(length or Polynomial.MAXLEN)+1] + + def __len__(self): + """Return len(self).""" + return len(self.coef) + + def __getitem__(self, term): + """Return coefficient of the corresponding term.""" + try: + return self.coef[term] + except IndexError: + return 0 + + def __iter__(self): + return iter(self.coef) + + def __repr__(self): + return 'Polynomial({})'.format(self.coef) + + def __add__(self, value): + """Return self+value.""" + length = max(len(self), len(value)) + return Polynomial((self[i]+value[i] for i in range(length))) + + def __mul__(self, value): + """Return self*value.""" + if isinstance(value, Polynomial): + l = [] + for i in range(min(len(self) + len(value) - 1, Polynomial.MAXLEN)): + l.append(sum(value[i - j] * c for j, c in enumerate(self) + if 0 <= i - j < len(value))) + return Polynomial(l) + + if isinstance(value, (int, float, complex, Fraction)): + return Polynomial((i * value for i in self.coef)) + + err = "unsupported operand type(s) for *: 'Polynomial' and '{}'" + raise TypeError(err.format(type(value).__name__)) + + def __rmul__(self, value): + """Return value*self.""" + return self * value + + def __pow__(self, value): + """Return self**value.""" + if value == 1: return self + tmp = self ** (value//2) + if value % 2: return tmp * self * tmp + return tmp * tmp + + +class ExpPoly(Polynomial): + """Exponential polynomial, with highest degree of 1000.""" + EXPPOLY = Polynomial((Fraction(1, factorial(i)) for i in range(Polynomial.MAXLEN))) + + def __init__(self, degree): + Polynomial.__init__(self, ExpPoly.EXPPOLY.coef, length=degree) + + +def chonso(m, a): + t = tuple(min(a.count(i), m) for i in set(a)) + d = {i: t.count(i) for i in set(t)} + Polynomial.MAXLEN = m + 1 + g = (ExpPoly(k) ** v for k, v in d.items()) + return reduce(mul, g, factorial(m))[-1].numerator + + +if __name__ == '__main__': + with open('chonso.inp') as fi, open('chonso.out', 'w') as fo: + n, m = map(int, fi.readline().split()) + a = tuple(int(i) for i in fi.readline().split())[:n] + print(chonso(m, a) % (10**12 + 7), file=fo) |