Lib/Fact_Mod.py at master · Ueeek/Lib · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#https://atcoder.jp/contests/tenka1-2014-final-open/submissions/12838089 "12写像乗ってそう
#強いので参考にしたい
# -*- coding: utf-8 -*-
class FactMod:
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない

    NとかRの値が固定なら、combとか、複数回呼び出すより先に、計算してしまってlistとかで持っておく方が良い。(TLE対策)
    '''

    def __init__(self, n, mod=10**9+7):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv_f: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv_f = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv_f.append(self.inv_f[-1]*i % mod)
        self.inv_f.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        if n<0:
            raise NotImplementedError
            return 0
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        if not(0<=r<=n):
            raise NotImplementedError
            return 0

        if r==0:
            return 1
        ret = self.f[n] * self.inv_f[n-r]*self.inv_f[r]
        ret %= self.mod
        return ret


    def perm(self, n, r):
        """
        nPrの値を返す
        """
        if not(0<=r<=n):
            raise NotImplementedError
            return 0
        ret = self.f[n] * self.inv_f[n-r]
        ret %= self.mod
        return ret

    def binomial(self,n,k):
        """
        二項係数を計算する
        :return: (n,k)
        """
        if n-k<0:
            raise NotImplementedError
            return 0
        ret = self.f[n]*self.inv_f[k]*self.inv_f[n-k]
        ret %= self.mod
        return ret


    def div(self,x,y):
        """
        x/yの値を返す
        このclassにいるべきじゃないな
        """
        return (x*pow(y,self.mod-2,self.mod))%self.mod

    def comb_low_r(self,n,r,MOD):
        """
        nCr=\frac{\Pi_{i=0}^{i=r-1}(n-i)}{\Pi_{i=1}^{i=r}(i)}
            FactMod(N,MOD)のNの値が大きいと、前計算が重くて、動かない。
            nCrのrが小さいという保証があるなら、以下のコードでも、十分早いはず
        """
        ret=1
        for i in range(r):#分子の計算
            ret*=(n-i)
            ret%=MOD
        for i in range(2,r+1):#分母の計算(powでinv(i)を求める。)
            ret*=pow(i,MOD-2,MOD)
            ret%=MOD
        return ret