競プロであったら嬉しいと思ったスニペットのまとめ

はじめに

競プロやっててほしいなと思ったスニペットとかをまとめて行くつもりです。そのうち増えていく予定です。
メインがPythonサブがC++なので、基本Pythonで書いていきますが余裕があったらC++のコードも足して行こうと思います。

また、全境界条件等検討できているとは限らないので責任はおえません。あしからず。

GCD(最大公約数),LCM(最小公倍数)

最大公約数はユークリッドの互除法によって構成します。LCMは2数の積/最大公約数です。
２数に関してのGCD及びLCMを繰り返すことで配列で与えた整数群に関してのGCD,LCMを計算します。

def gcd_core(a, b):
    if b == 0:
        return a
    else:
        return gcd_core(b, a % b)

def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)):
        g = gcd_core(g, arr[i])
    return g

def lcm_core(a,b):
    g = gcd_core(a,b)
    return (a*b)//g

def lcm(arr):
    l = lcm_core(arr[0],arr[1])
    for i in range(2,len(arr)):
        l = lcm_core(l,arr[i])
    return l

Union-Find木(連結要素)

UF木です。経路圧縮などは根をたどるときのつなぎ直ししか入れていないため、もっと最適化が必要な場面が出てくるかもしれません。indep()で連結要素の数を数えることができます。ノードが1 indexから始まる場合はn+1でインスタンスを作成して、ノード0を捨てます。

class uf_tree():

    def __init__(self,n):
        self.n = n
        self.par = [i for i in range(n)]

    def indep(self):
        dep =0
        for i in range(self.n):
            if i == self.par[i]:
                dep += 1

        return dep

    def unite(self,child,mas):
        if self.root(child) == self.root(mas):
            return
        else:
            self.par[self.root(child)] = self.root(mas)

    def root(self,i):
        if self.par[i] == i:
            return i
        else:
            self.par[i] = self.root(self.par[i])
            return self.par[i]

    def same(self,x,y):
        if self.root(x) == self.root(y):
            return True
        else:
            return False

素因数分解(ためしわり)

返り値はディクショナリです。
{因数:べき数}の形になっています。
素数のときはからのディクショナリが返ってきます。

def factorize(N):
    up = int(np.sqrt(N))+2
    out = {}

    for i in range(2,up):
        if N%i == 0:
            temp = N
            count = 0
            while(True):
                N = N//i
                count += 1
                if N%i != 0:
                    break
            out[i] = count
        else:
            continue
    return out

print(factorize(60))
print(factorize(10**9+7))

{2: 2, 3: 1, 5: 1}
{}

modありべき乗

これ掛け算そのままは多分あまり使うことはなくて、行列の掛け算とかもう少しコストの掛かる累乗計算で力を発揮すると思います。
あとこれ再帰だとちょっと遅いみたいなので、困るようならfor版書きますが、再帰のほうがプログラムが見やすいので、ひとまず再帰を使います。

def large_expo(x,n,mod):
    if n == 2:
        return (x*x)%mod
    elif n %2 == 1:
        return (large_expo(x,n-1,mod)*x)%mod
    else:
        temp = large_expo(x,n//2,mod)%mod
        return (temp*temp)%mod

modありnCk(組み合わせ)

フェルマーの小定理による逆元を利用。

nCkのnとmodで初期化します。複数回計算する必要がある場合はnを大きい方にあわせてとっておけば小さい方も計算できます。

便利なのでついでにこのクラスにpermutaionと逆元も実装しておきます。

class combination_mod:
    def __init__(self,n,mod):
        self.mod = mod
        self.fact = [1 for i in range(n)]
        for i in range(2,n+1):
            self.fact[i-1] = (self.fact[i-2]*i)%mod

    def expo(self,x,n):
        if n == 2:
            return (x * x) % self.mod
        elif n % 2 == 1:
            return (self.expo(x, n - 1) * x) % self.mod
        else:
            temp = self.expo(x, n // 2) % self.mod
            return (temp * temp) % self.mod
    def comb(self,n,k):
        a = (self.fact[n]*self.expo(self.fact[k],self.mod-2))%self.mod
        return (a*self.expo(self.fact[n-k],self.mod-2))%self.mod
    def invm(self,x):
        return (self.expo(self.fact[x],self.mod-2))%self.mod
    def perm(self,n,k):
        return (self.fact[n]*self.expo(self.fact[n-k],self.mod-2))%self.mod

cm = combination_mod(100,10**9+7)

print(cm.comb(4,2))
print(cm.comb(100,1))
print(cm.comb(100,50))

6
100
538992043