結果
| 問題 | No.2825 Sum of Scores of Sets of Specified Sections |
| ユーザー |
 🦠みどりむし
|
| 提出日時 | 2024-06-22 14:09:56 |
| 言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,621 bytes |
| コンパイル時間 | 119 ms |
| コンパイル使用メモリ | 13,184 KB |
| 実行使用メモリ | 52,160 KB |
| 最終ジャッジ日時 | 2024-07-26 20:01:55 |
| 合計ジャッジ時間 | 5,720 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 485 ms
52,160 KB |
| testcase_01 | TLE | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
ソースコード
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()