cp-library
This documentation is automatically generated by online-judge-tools/verification-helper
cp_library/math/linalg/mat/mod/mat_cls.py
- View this file on GitHub
- Last update: 2025-08-24 20:27:05+09:00
Depends on
cp_library/io/io_base_cls.py
- cp_library/io/parsable_cls.py
- cp_library/io/parser_cls.py
- cp_library/math/linalg/elm_wise_in_place_mixin.py
- cp_library/math/linalg/elm_wise_mixin.py
Code
import cp_library.__header__
from typing import Container, Sequence
from numbers import Number
from cp_library.io.parsable_cls import Parsable
import cp_library.math.__header__
import cp_library.math.linalg.__header__
from cp_library.math.linalg.elm_wise_in_place_mixin import ElmWiseInPlaceMixin
import cp_library.math.linalg.mat.__header__
import cp_library.math.linalg.mat.mod.__header__
class Mat(Parsable, Container, ElmWiseInPlaceMixin):
def __init__(self, flat, N, M):
self.data, self.N, self.M = flat, N, M
def elm_wise(self, other, op):
cls = type(self)
if isinstance(other, Number):
return cls([op(elm, other) for elm in self.data])
if isinstance(other, Sequence):
return cls([op(self.data[i], elm) for i, elm in enumerate(other)])
raise ValueError("Operand must be a number or a tuple of the same length")
def ielm_wise(self, other, op):
data = self.data
if isinstance(other, Number):
for i in range(len(data)):
data[i] = op(data[i], other)
elif isinstance(other, Sequence) and len(data) == len(other):
for i, elm in enumerate(other):
data[i] = op(data[i], elm)
else:
raise ValueError("Operand must be a number or a list of the same length")
return self
def __len__(self):
return self.N
def __getitem__(self, ij: tuple[int, int]):
i, j = ij
return self.data[i*self.M+j]
def __setitem__(self, ij: tuple[int, int], val: int):
i, j = ij
self.data[i*self.M+j] = val
def __contains__(self, x: int) -> bool:
return x in self.data
def __matmul__(A,B):
assert A.M == B.N, f"Dimension mismatch {A.M = } {B.N = }"
N,M = A.N, B.M
cls = type(A)
R = cls([0]*(M*N))
for irow in range(0,N*M,M):
for k in range(A.M):
krow, a = k*M, A.data[irow+k]
for j in range(M):
R.data[irow+j] = B.data[krow+j]*a + R.data[irow+j]
return R
def __pow__(A,K):
R = A[:] if K & 1 else type(A).identity(A.N)
for i in range(1,K.bit_length()):
A = A @ A
if K >> i & 1:
R = R @ A
return R
@classmethod
def identity(cls, N):
data = [0]*(N*N)
for i in range(0,N*N,N+1): data[i] = 1
return cls(data)
def copy(self):
cls = type(self)
obj = cls.__new__(cls)
obj.N, obj.M, obj.data = self.N, self.M, self.data
return obj
@classmethod
def compile(cls, N: int, M: int, T: type = int):
elm, size = Parser.compile(T), N*M
def parse(io: IOBase):
return cls([elm(io) for _ in range(size)])
return parse
def __repr__(self) -> str:
return '\n'.join(' '.join(str(elm) for elm in row) for row in self)
from cp_library.io.io_base_cls import IOBase
from cp_library.io.parser_cls import Parser'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
https://kobejean.github.io/cp-library
'''
from typing import Container, Sequence
from numbers import Number
from types import GenericAlias
class Parsable:
@classmethod
def compile(cls):
def parser(io: 'IOBase'): return cls(next(io))
return parser
@classmethod
def __class_getitem__(cls, item): return GenericAlias(cls, item)
import operator
from math import hypot
class ElmWiseMixin:
def elm_wise(self, other, op):
if isinstance(other, Sequence):
return self.__class__(op(self[i], y) for i, y in enumerate(self, other))
if isinstance(other, Number):
return self.__class__(op(x, other) for x in self)
raise ValueError("Operand must be a number or a tuple of the same length")
def __add__(self, other): return self.elm_wise(other, operator.add)
def __radd__(self, other): return self.elm_wise(other, operator.add)
def __sub__(self, other): return self.elm_wise(other, operator.sub)
def __rsub__(self, other): return self.elm_wise(other, lambda x,y: operator.sub(y,x))
def __mul__(self, other): return self.elm_wise(other, operator.mul)
def __rmul__(self, other): return self.elm_wise(other, operator.mul)
def __truediv__(self, other): return self.elm_wise(other, operator.truediv)
def __rtruediv__(self, other): return self.elm_wise(other, lambda x,y: operator.truediv(y,x))
def __floordiv__(self, other): return self.elm_wise(other, operator.floordiv)
def __rfloordiv__(self, other): return self.elm_wise(other, lambda x,y: operator.floordiv(y,x))
def __mod__(self, other): return self.elm_wise(other, operator.mod)
def distance(self: 'ElmWiseMixin', other: 'ElmWiseMixin'):
diff = other-self
return hypot(*diff)
def magnitude(vec: 'ElmWiseMixin'):
return hypot(*vec)
def norm(vec: 'ElmWiseMixin'):
return vec / vec.magnitude()
class ElmWiseInPlaceMixin(ElmWiseMixin):
def ielm_wise(self, other, op):
if isinstance(other, Number):
for i in range(len(self)):
self[i] = op(self[i], other)
elif isinstance(other, Sequence) and len(self) == len(other):
for i in range(len(self)):
self[i] = op(self[i], other[i])
else:
raise ValueError("Operand must be a number or a list of the same length")
return self
def __iadd__(self, other): return self.ielm_wise(other, operator.add)
def __isub__(self, other): return self.ielm_wise(other, operator.sub)
def __imul__(self, other): return self.ielm_wise(other, operator.mul)
def __itruediv__(self, other): return self.ielm_wise(other, operator.truediv)
def __ifloordiv__(self, other): return self.ielm_wise(other, operator.floordiv)
def __imod__(self, other): return self.ielm_wise(other, operator.mod)
class Mat(Parsable, Container, ElmWiseInPlaceMixin):
def __init__(self, flat, N, M):
self.data, self.N, self.M = flat, N, M
def elm_wise(self, other, op):
cls = type(self)
if isinstance(other, Number):
return cls([op(elm, other) for elm in self.data])
if isinstance(other, Sequence):
return cls([op(self.data[i], elm) for i, elm in enumerate(other)])
raise ValueError("Operand must be a number or a tuple of the same length")
def ielm_wise(self, other, op):
data = self.data
if isinstance(other, Number):
for i in range(len(data)):
data[i] = op(data[i], other)
elif isinstance(other, Sequence) and len(data) == len(other):
for i, elm in enumerate(other):
data[i] = op(data[i], elm)
else:
raise ValueError("Operand must be a number or a list of the same length")
return self
def __len__(self):
return self.N
def __getitem__(self, ij: tuple[int, int]):
i, j = ij
return self.data[i*self.M+j]
def __setitem__(self, ij: tuple[int, int], val: int):
i, j = ij
self.data[i*self.M+j] = val
def __contains__(self, x: int) -> bool:
return x in self.data
def __matmul__(A,B):
assert A.M == B.N, f"Dimension mismatch {A.M = } {B.N = }"
N,M = A.N, B.M
cls = type(A)
R = cls([0]*(M*N))
for irow in range(0,N*M,M):
for k in range(A.M):
krow, a = k*M, A.data[irow+k]
for j in range(M):
R.data[irow+j] = B.data[krow+j]*a + R.data[irow+j]
return R
def __pow__(A,K):
R = A[:] if K & 1 else type(A).identity(A.N)
for i in range(1,K.bit_length()):
A = A @ A
if K >> i & 1:
R = R @ A
return R
@classmethod
def identity(cls, N):
data = [0]*(N*N)
for i in range(0,N*N,N+1): data[i] = 1
return cls(data)
def copy(self):
cls = type(self)
obj = cls.__new__(cls)
obj.N, obj.M, obj.data = self.N, self.M, self.data
return obj
@classmethod
def compile(cls, N: int, M: int, T: type = int):
elm, size = Parser.compile(T), N*M
def parse(io: IOBase):
return cls([elm(io) for _ in range(size)])
return parse
def __repr__(self) -> str:
return '\n'.join(' '.join(str(elm) for elm in row) for row in self)
class IOBase:
@property
def char(io) -> bool: ...
@property
def writable(io) -> bool: ...
def __next__(io) -> str: ...
def write(io, s: str) -> None: ...
def readline(io) -> str: ...
def readtoken(io) -> str: ...
def readtokens(io) -> list[str]: ...
def readints(io) -> list[int]: ...
def readdigits(io) -> list[int]: ...
def readnums(io) -> list[int]: ...
def readchar(io) -> str: ...
def readchars(io) -> str: ...
def readinto(io, lst: list[str]) -> list[str]: ...
def readcharsinto(io, lst: list[str]) -> list[str]: ...
def readtokensinto(io, lst: list[str]) -> list[str]: ...
def readintsinto(io, lst: list[int]) -> list[int]: ...
def readdigitsinto(io, lst: list[int]) -> list[int]: ...
def readnumsinto(io, lst: list[int]) -> list[int]: ...
def wait(io): ...
def flush(io) -> None: ...
def line(io) -> list[str]: ...
import typing
from typing import Callable, Collection
class Parser:
def __init__(self, spec): self.parse = Parser.compile(spec)
def __call__(self, io: IOBase): return self.parse(io)
@staticmethod
def compile_type(cls, args = ()):
if issubclass(cls, Parsable): return cls.compile(*args)
elif issubclass(cls, (Number, str)):
def parse(io: IOBase): return cls(next(io))
return parse
elif issubclass(cls, tuple): return Parser.compile_tuple(cls, args)
elif issubclass(cls, Collection): return Parser.compile_collection(cls, args)
elif callable(cls):
def parse(io: IOBase): return cls(next(io))
return parse
else: raise NotImplementedError()
@staticmethod
def compile(spec=int):
if isinstance(spec, (type, GenericAlias)):
cls, args = typing.get_origin(spec) or spec, typing.get_args(spec) or tuple()
return Parser.compile_type(cls, args)
elif isinstance(offset := spec, Number):
cls = type(spec)
def parse(io: IOBase): return cls(next(io)) + offset
return parse
elif isinstance(args := spec, tuple): return Parser.compile_tuple(type(spec), args)
elif isinstance(args := spec, Collection): return Parser.compile_collection(type(spec), args)
elif isinstance(fn := spec, Callable):
def parse(io: IOBase): return fn(next(io))
return parse
else: raise NotImplementedError()
@staticmethod
def compile_line(cls, spec=int):
if spec is int:
def parse(io: IOBase): return cls(io.readnums())
elif spec is str:
def parse(io: IOBase): return cls(io.line())
else:
fn = Parser.compile(spec)
def parse(io: IOBase): return cls((fn(io) for _ in io.wait()))
return parse
@staticmethod
def compile_repeat(cls, spec, N):
fn = Parser.compile(spec)
def parse(io: IOBase): return cls([fn(io) for _ in range(N)])
return parse
@staticmethod
def compile_children(cls, specs):
fns = tuple((Parser.compile(spec) for spec in specs))
def parse(io: IOBase): return cls([fn(io) for fn in fns])
return parse
@staticmethod
def compile_tuple(cls, specs):
if isinstance(specs, (tuple,list)) and len(specs) == 2 and specs[1] is ...: return Parser.compile_line(cls, specs[0])
else: return Parser.compile_children(cls, specs)
@staticmethod
def compile_collection(cls, specs):
if not specs or len(specs) == 1 or isinstance(specs, set):
return Parser.compile_line(cls, *specs)
elif (isinstance(specs, (tuple,list)) and len(specs) == 2 and isinstance(specs[1], int)):
return Parser.compile_repeat(cls, specs[0], specs[1])
else:
raise NotImplementedError()