cp_library/math/fps/fps_deriv_fn.py

• View this file on GitHub
• Last update: 2025-03-30 20:17:47+09:00

Depends on

• cp_library/math/mod/mint_cls.py

Required by

• cp_library/math/fps/fps_exp_fn.py
• cp_library/math/fps/fps_log_fn.py
• cp_library/math/fps/fps_pow_fn.py
• cp_library/math/table/stirling1_k_fn.py
• cp_library/math/table/stirling2_k_fn.py

Verified with

• test/library-checker/enumerative-combinatorics/stirling_number_of_the_first_kind_fixed_k.test.py
• test/library-checker/enumerative-combinatorics/stirling_number_of_the_second_kind_fixed_k.test.py
• test/library-checker/polynomial/exp_of_formal_power_series.test.py
• test/library-checker/polynomial/log_of_formal_power_series.test.py
• test/library-checker/polynomial/pow_of_formal_power_series.test.py

Code

import cp_library.math.fps.__header__

def fps_deriv(P: list[int]):
    mod = mint.mod
    return [P[i]*i%mod for i in range(1,len(P))]

from cp_library.math.mod.mint_cls import mint

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''

def fps_deriv(P: list[int]):
    mod = mint.mod
    return [P[i]*i%mod for i in range(1,len(P))]


    
class mint(int):
    mod: int
    zero: 'mint'
    one: 'mint'
    two: 'mint'
    cache: list['mint']

    def __new__(cls, *args, **kwargs):
        if 0<= (x := int(*args, **kwargs)) <= 2:
            return cls.cache[x]
        else:
            return cls.fix(x)

    @classmethod
    def set_mod(cls, mod: int):
        mint.mod = cls.mod = mod
        mint.zero = cls.zero = cls.cast(0)
        mint.one = cls.one = cls.fix(1)
        mint.two = cls.two = cls.fix(2)
        mint.cache = cls.cache = [cls.zero, cls.one, cls.two]

    @classmethod
    def fix(cls, x): return cls.cast(x%cls.mod)

    @classmethod
    def cast(cls, x): return super().__new__(cls,x)

    @classmethod
    def mod_inv(cls, x):
        a,b,s,t = int(x), cls.mod, 1, 0
        while b: a,b,s,t = b,a%b,t,s-a//b*t
        if a == 1: return cls.fix(s)
        raise ValueError(f"{x} is not invertible in mod {cls.mod}")
    
    @property
    def inv(self): return mint.mod_inv(self)

    def __add__(self, x): return mint.fix(super().__add__(x))
    def __radd__(self, x): return mint.fix(super().__radd__(x))
    def __sub__(self, x): return mint.fix(super().__sub__(x))
    def __rsub__(self, x): return mint.fix(super().__rsub__(x))
    def __mul__(self, x): return mint.fix(super().__mul__(x))
    def __rmul__(self, x): return mint.fix(super().__rmul__(x))
    def __floordiv__(self, x): return self * mint.mod_inv(x)
    def __rfloordiv__(self, x): return self.inv * x
    def __truediv__(self, x): return self * mint.mod_inv(x)
    def __rtruediv__(self, x): return self.inv * x
    def __pow__(self, x): 
        return self.cast(super().__pow__(x, self.mod))
    def __neg__(self): return mint.mod-self
    def __pos__(self): return self
    def __abs__(self): return self

Back to top page