結果

問題 No.1105 Many Triplets
コンテスト
ユーザー hahho
提出日時 2024-08-06 16:50:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 60 ms / 2,000 ms
コード長 10,742 bytes
コンパイル時間 362 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 70,016 KB
最終ジャッジ日時 2024-08-06 16:50:51
合計ジャッジ時間 3,035 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

def modinv(x: int, mod: int) -> int:
    """
    Z/(mod Z)上でのxの逆元

    :param x: 整数
    :param mod: 整数
    :return: x * y % mod = 1を満たすy
    """
    s, ps, r, pr = 0, 1, mod, x
    while r != 0:
        pr, (q, r) = r, divmod(pr, r)
        ps, s = s, ps - q * s
    if pr == 1:
        return ps if ps >= 0 else ps + mod
    raise ValueError("base is not invertible for the given modulus")


def modpow(x, k, mod):
    """
    Z/(mod Z)上でのxのk乗

    :param x: 整数
    :param k: 整数
    :param mod: 整数
    :return: x ** k % mod
    """
    if k < 0:
        x = modinv(x, mod)
        k = -k
    r = 1
    while k != 0:
        if k & 1:
            r = (r * x) % mod
        x = (x * x) % mod
        k >>= 1
    return r

intadd = int.__add__
intsub = int.__sub__
intmul = int.__mul__

MOD = 10**9 + 7

class ModInt(int):

    @classmethod
    def normalized(cls, v):
        return ModInt(v % MOD)

    def __neg__(self):
        return ModInt(intsub(MOD, self) if self != 0 else 0)

    def __add__(self, other):
        x = intadd(self, other)
        return ModInt(x if x < MOD else x - MOD)

    def __sub__(self, other):
        x = intsub(self, other)
        return ModInt(x if x >= 0 else x + MOD)

    def __rsub__(self, other):
        x = intsub(other, self)
        return ModInt(x if x >= 0 else x + MOD)

    def __mul__(self, other):
        return ModInt(intmul(self, other) % MOD)

    def __truediv__(self, other):
        return self * ModInt(other).inv

    def __rtruediv__(self, other):
        return self.inv * other

    __radd__ = __add__
    __rmul__ = __mul__
    __floordiv__ = __truediv__
    __rfloordiv__ = __rtruediv__

    def __pow__(self, other, **kwargs):
        return ModInt(modpow(int(self), int(other), MOD))

    @property
    def inv(self):
        return ModInt(modinv(int(self), MOD))

    @classmethod
    def sum(cls, iterable):
        r = 0
        for v in iterable:
            r += int(v)
        return ModInt(r % MOD)

    @classmethod
    def product(cls, iterable):
        r = ModInt(1)
        for v in iterable:
            r *= v
        return r


class Array2dView:
    def __init__(self, arr, i_indices, j_indices):
        self.arr = arr
        self.i_indices = i_indices
        self.j_indices = j_indices
        self.n = len(i_indices)
        self.m = len(j_indices)

    def _get_view(self, i, j):
        i = self.i_indices[i]
        j = self.j_indices[j]
        return Array2dView(self.arr, i, j)

    def get_ind(self, i, j):
        return self.i_indices[i] + self.j_indices[j]

    def __getitem__(self, index):
        i, j = index
        try:
            return self.arr[self.get_ind(i, j)]
        except TypeError:
            return self._get_view(i, j)

    def __setitem__(self, index, value):
        i, j = index
        try:
            self.arr[self.get_ind(i, j)] = value
        except TypeError:
            x = self._get_view(i, j)
            for i in x.i_indices:
                for j in x.j_indices:
                    self.arr[i + j] = value

    def __iter__(self):
        for i in self.i_indices:
            for j in self.j_indices:
                yield self.arr[i + j]

    def __reversed__(self):
        for i in reversed(self.i_indices):
            for j in reversed(self.j_indices):
                yield self.arr[i + j]

    def __str__(self):
        m = max(len(str(v)) for v in self)
        res = [''] * len(self.i_indices)
        row = [''] * (len(self.j_indices) + 2)
        for ri, i in enumerate(self.i_indices):
            if ri == 0:
                row[0] = '['
            else:
                row[0] = ' '
            if ri == len(self.i_indices) - 1:
                row[-1] = ']\n'
            for rj, j in enumerate(self.j_indices):
                row[rj + 1] = f'{str(self.arr[i + j]):>{m + 1}}'
            res[ri] = ''.join(row)
        return '\n'.join(res)

    def copy(self):
        return Array2d(len(self.i_indices), len(self.j_indices), list(self))

class Array2d:
    def __init__(self, n, m, arr):
        self.n = n
        self.m = m
        self.arr = arr

    @classmethod
    def full(cls, n, m, fill_value):
        return cls(n, m, [fill_value] * (n * m))

    @classmethod
    def from_list(cls, lst):
        n, m = len(lst), len(lst[0])
        arr = [lst[0]] * (n * m)
        k = 0
        for row in lst:
            for v in row:
                arr[k] = v
                k += 1
        return cls(n, m, arr)

    def _get_view(self, i, j):
        i = tuple(range(0, self.n * self.m, self.m))[i]
        j = tuple(range(self.m))[j]
        return Array2dView(self.arr, i, j)

    def get_ind(self, i, j):
        return i * self.m + j

    def __getitem__(self, index):
        try:
            return self.arr[self.get_ind(*index)]
        except TypeError:
            return self._get_view(*index)

    def __setitem__(self, index, value):
        try:
            self.arr[self.get_ind(*index)] = value
        except TypeError:
            x = self._get_view(*index)
            for i in x.i_indices:
                for j in x.j_indices:
                    self.arr[i + j] = value

    def __iter__(self):
        return iter(self.arr)

    def __reversed__(self):
        return reversed(self.arr)

    def __str__(self):
        m = max(len(str(v)) for v in self)
        res = [''] * self.n
        row = [''] * (self.m + 2)
        for i in range(self.n):
            if i == 0:
                row[0] = '['
            else:
                row[0] = ' '
            if i == self.n - 1:
                row[-1] = ']\n'
            for j in range(self.m):
                row[j + 1] = f'{str(self.arr[i * self.m + j]):>{m + 1}}'
            res[i] = ''.join(row)
        return '\n'.join(res)

    __repr__ = __str__

    def __eq__(self, other):
        return self.arr == other.arr

    def copy(self):
        return self.__class__(self.n, self.m, self.arr[:])

    @property
    def t(self):
        arr = [self.arr[0]] * (len(self.arr))
        x = 0
        for i in range(self.n):
            for j in range(self.m):
                arr[j * self.n + i] = self.arr[x]
                x += 1
        return self.__class__(self.m, self.n, arr)


def get_general_matrix(zero, one):
    class Matrix(Array2d):
        ZERO = zero
        ONE = one

        @classmethod
        def zeros(cls, n, m):
            return cls.full(n, m, cls.ZERO)

        @classmethod
        def ones(cls, n, m):
            return cls.full(n, m, cls.ONE)

        def __add__(self, other):
            if self.m != other.m or self.n != other.n:
                raise ValueError(f'Cannot add matrices ({self.n}, {self.m}) and ({other.n}, {other.m})')
            return Matrix(self.n, self.m, [x + y for x, y in zip(self.arr, other.arr)])

        def __iadd__(self, other):
            if self.m != other.m or self.n != other.n:
                raise ValueError(f'Cannot multiply matrices ({self.n}, {self.m}) and ({other.n}, {other.m})')
            for i, v in enumerate(other.arr):
                self.arr[i] += v
            return self

        def __sub__(self, other):
            if self.m != other.m or self.n != other.n:
                raise ValueError(f'Cannot subtract matrices ({self.n}, {self.m}) and ({other.n}, {other.m})')
            return Matrix(self.n, self.m, [x - y for x, y in zip(self.arr, other.arr)])

        def __isub__(self, other):
            if self.m != other.m or self.n != other.n:
                raise ValueError(f'Cannot multiply matrices ({self.n}, {self.m}) and ({other.n}, {other.m})')
            for i, v in enumerate(other.arr):
                self.arr[i] -= v
            return self

        def __mul__(self, other):
            if self.m != other.m or self.n != other.n:
                raise ValueError(f'Cannot multiply matrices ({self.n}, {self.m}) and ({other.n}, {other.m})')
            return Matrix(self.n, self.m, [x * y for x, y in zip(self.arr, other.arr)])

        def __imul__(self, other):
            if self.m != other.m or self.n != other.n:
                raise ValueError(f'Cannot multiply matrices ({self.n}, {self.m}) and ({other.n}, {other.m})')
            for i, v in enumerate(other.arr):
                self.arr[i] *= v
            return self

        def __truediv__(self, other):
            if self.m != other.m or self.n != other.n:
                raise ValueError(f'Cannot multiply matrices ({self.n}, {self.m}) and ({other.n}, {other.m})')
            return Matrix(self.n, self.m, [x / y for x, y in zip(self.arr, other.arr)])

        def __matmul__(self, other):
            if self.m != other.n:
                raise ValueError(f'Cannot dot multiply matrices ({self.n}, {self.m}) and ({other.n}, {other.m})')

            res = self.full(self.n, other.m, self.ZERO)

            for i in range(self.n):
                for j in range(other.m):
                    c = self.ZERO
                    for k in range(self.m):
                        c += self[i, k] * other[k, j]
                    res[i, j] = c
            return res

        def __imatmul__(self, other):
            if self.m != other.n:
                raise ValueError(f'Cannot multiply matrices ({self.n}, {self.m}) and ({other.n}, {other.m})')
            if self is other or self.m != other.m:
                return self @ other

            row = [self.ZERO] * self.m
            for i in range(self.n):
                t = i * self.m
                for j in range(self.m):
                    row[j] = self.arr[j + t]
                for j in range(other.m):
                    c = self.ZERO
                    for k in range(self.m):
                        c += row[k] * other[k, j]
                    self[i, j] = c
            return self

        def __pow__(self, power, modulo=None):
            if self.n != self.m:
                raise ValueError('pow is supported only for square matrix')
            k = self.n
            res = Matrix.full(k, k, self.ZERO)
            for i in range(k):
                res[i, i] = self.ONE

            m = self
            while power > 0:
                if power & 1:
                    res @= m
                m @= m
                power >>= 1
            return res

    return Matrix

modint = ModInt

n = int(input())
a,b,c = map(int, input().split())

M = get_general_matrix(modint(0), modint(1))

m = M.from_list([[modint(1), -modint(1), modint(0),],
                 [modint(0), modint(1), -modint(1),],
                 [-modint(1), modint(0), modint(1),]])
m **= n-1
v = M.from_list([[modint.normalized(a)],[modint.normalized(b)],[modint.normalized(c)]])

v = m@v
print(v[0, 0], v[1, 0], v[2, 0])
0