結果

問題 No.2825 Sum of Scores of Sets of Specified Sections
コンテスト
ユーザー みどりむし🦠
提出日時 2024-06-22 14:09:56
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 5,621 bytes
コンパイル時間 119 ms
コンパイル使用メモリ 13,184 KB
実行使用メモリ 52,160 KB
最終ジャッジ日時 2024-07-26 20:01:55
合計ジャッジ時間 5,720 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import numpy as np
from itertools import product

class ModInt998244353:
    def __init__(self, value=0):
        self.mod = 998244353
        if isinstance(value, ModInt998244353):
            self.value = value.value
        else:
            self.value = value % self.mod

    def __add__(self, other):
        if isinstance(other, ModInt998244353):
            return ModInt998244353(self.value + other.value)
        return ModInt998244353(self.value + other)

    def __sub__(self, other):
        if isinstance(other, ModInt998244353):
            return ModInt998244353(self.value - other.value)
        return ModInt998244353(self.value - other)

    def __mul__(self, other):
        if isinstance(other, ModInt998244353):
            return ModInt998244353(self.value * other.value)
        return ModInt998244353(self.value * other)

    def __truediv__(self, other):
        if isinstance(other, ModInt998244353):
            return self * other.inv()
        return self * ModInt998244353(other).inv()

    def __floordiv__(self, other):
        return self.__truediv__(other)

    def __eq__(self, other):
        if isinstance(other, ModInt998244353):
            return self.value == other.value
        return self.value == other

    def __ne__(self, other):
        return not self.__eq__(other)

    def __neg__(self):
        return ModInt998244353(-self.value)

    def __pow__(self, power):
        if isinstance(power, ModInt998244353):
            power = power.value
        result = ModInt998244353(1)
        base = ModInt998244353(self.value)
        while power:
            if power % 2:
                result *= base
            base *= base
            power //= 2
        return result

    def inv(self):
        return self.__pow__(self.mod - 2)

    def __int__(self):
        return self.value

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return f"ModInt998244353({self.value})"

class Matrix:
    def __init__(self, n, m):
        self._height = n
        self._width = m
        self._data = [[ModInt998244353() for _ in range(m)] for _ in range(n)]

    @classmethod
    def identity(cls, n):
        res = cls(n, n)
        for i in range(n):
            res._data[i][i] = ModInt998244353(1)
        return res

    def __getitem__(self, p):
        return self._data[p]

    def __setitem__(self, p, value):
        self._data[p] = value

    def __iadd__(self, rhs):
        assert self._height == rhs._height and self._width == rhs._width
        for i in range(self._height):
            for j in range(self._width):
                self._data[i][j] += rhs._data[i][j]
        return self

    def __add__(self, rhs):
        assert self._height == rhs._height and self._width == rhs._width
        result = Matrix(self._height, self._width)
        for i in range(self._height):
            for j in range(self._width):
                result._data[i][j] = self._data[i][j] + rhs._data[i][j]
        return result

    def __radd__(self, lhs):
        return self.__add__(lhs)

    def __sub__(self, rhs):
        assert self._height == rhs._height and self._width == rhs._width
        result = Matrix(self._height, self._width)
        for i in range(self._height):
            for j in range(self._width):
                result._data[i][j] = self._data[i][j] - rhs._data[i][j]
        return result

    def __mul__(self, rhs):
        assert self._width == rhs._height
        product = Matrix(self._height, rhs._width)
        for i in range(self._height):
            for j in range(rhs._width):
                for k in range(self._width):
                    product._data[i][j] += self._data[i][k] * rhs._data[k][j]
        return product

    def transpose(self):
        res = Matrix(self._width, self._height)
        for i in range(self._height):
            for j in range(self._width):
                res._data[j][i] = self._data[i][j]
        self._data = res._data
        self._height = res._height
        self._width = res._width
        return self

    def det(self):
        X = [row[:] for row in self._data]
        res = ModInt998244353(1)
        for i in range(self._width):
            pivot = -1
            for j in range(i, self._width):
                if X[j][i] != ModInt998244353(0):
                    pivot = j
                    break

            if pivot == -1:
                return ModInt998244353(0)

            if i != pivot:
                res *= ModInt998244353(-1)
                X[i], X[pivot] = X[pivot], X[i]

            res *= X[i][i]
            inv = ModInt998244353(1) / X[i][i]
            for j in range(i, self._width):
                X[i][j] *= inv

            for j in range(i + 1, self._width):
                v = X[j][i]
                for k in range(i, self._width):
                    X[j][k] -= X[i][k] * v

        return res

    def __str__(self):
        return '\n'.join(' '.join(str(cell) for cell in row) for row in self._data)

def matrix_read(n, m, data, index):
    mat = Matrix(n, m)
    for i in range(n):
        for j in range(m):
            mat[i][j] = ModInt998244353(int(data[index]))
            index += 1
    return mat, index

def main():
    input = sys.stdin.read
    data = input().split()
    index = 0

    n = int(data[index])
    m = int(data[index + 1])
    index += 2

    A, index = matrix_read(n, m, data, index)
    B, index = matrix_read(n, m, data, index)

    B.transpose()
    result = (Matrix.identity(n) + (A * B)).det() - ModInt998244353(1)
    print(result)

if __name__ == "__main__":
    main()
0