結果

問題 No.2825 Sum of Scores of Sets of Specified Sections
ユーザー chineristACchineristAC
提出日時 2024-07-26 22:32:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 553 ms / 3,000 ms
コード長 2,965 bytes
コンパイル時間 634 ms
コンパイル使用メモリ 82,464 KB
実行使用メモリ 83,248 KB
最終ジャッジ日時 2024-07-26 22:32:45
合計ジャッジ時間 6,166 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 46 ms
57,188 KB
testcase_01 AC 527 ms
83,248 KB
testcase_02 AC 534 ms
83,228 KB
testcase_03 AC 553 ms
83,136 KB
testcase_04 AC 115 ms
78,040 KB
testcase_05 AC 60 ms
72,316 KB
testcase_06 AC 54 ms
65,428 KB
testcase_07 AC 84 ms
77,976 KB
testcase_08 AC 79 ms
77,856 KB
testcase_09 AC 60 ms
71,648 KB
testcase_10 AC 59 ms
71,080 KB
testcase_11 AC 60 ms
66,456 KB
testcase_12 AC 51 ms
65,200 KB
testcase_13 AC 59 ms
72,836 KB
testcase_14 AC 135 ms
77,960 KB
testcase_15 AC 129 ms
77,900 KB
testcase_16 AC 130 ms
77,796 KB
testcase_17 AC 132 ms
77,940 KB
testcase_18 AC 134 ms
77,908 KB
testcase_19 AC 132 ms
77,788 KB
testcase_20 AC 131 ms
78,028 KB
testcase_21 AC 145 ms
78,000 KB
testcase_22 AC 132 ms
78,140 KB
testcase_23 AC 130 ms
77,792 KB
testcase_24 AC 83 ms
77,708 KB
testcase_25 AC 82 ms
77,660 KB
testcase_26 AC 84 ms
77,700 KB
testcase_27 AC 83 ms
77,632 KB
testcase_28 AC 47 ms
58,376 KB
testcase_29 AC 45 ms
57,212 KB
testcase_30 AC 46 ms
57,672 KB
testcase_31 AC 45 ms
57,080 KB
testcase_32 AC 271 ms
79,172 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import permutations
from heapq import *
from collections import deque
import random
import bisect
from math import factorial

input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

mod = 998244353

def mat_mul(X,Y):
    n,m = len(X),len(Y[0])
    res = [[0 for j in range(m)] for i in range(n)]
    for i in range(n):
        for j in range(m):
            for k in range(len(Y)):
                res[i][j] += X[i][k] * Y[k][j]
                res[i][j] %= mod
    return res

def det(G, mod = 998244353):
    N = len(G)
    res = 1
    for i in range(N):
        for h in range(i, N):
            if G[h][i]:
                break
        if i != h:
            G[i], G[h] = G[h][:], G[i][:]
            res = res * (-1) % mod
        gii = G[i][i]
        res = res*gii%mod
        giiv = pow(gii, mod-2, mod)
        for w in range(i, N):
            G[i][w] = G[i][w]*giiv%mod

        for j in range(i+1, N):
            gji = G[j][i]
            if gji:
                for w in range(i, N):
                    G[j][w] = (G[j][w]-gji*G[i][w])%mod
    return res

def solve_lie(H,W,A,B):
    dp0 = [[0]*W for i in range(H)]
    dp1 = [[0]*W for i in range(H)]
    for i in range(H):
        dp0[i][0] = A[i][0] * B[i][0] % mod
        dp1[i][0] = A[i][0] * B[i][0] % mod
        if i!=0:
            dp1[i][0] += dp1[i-1][0]
            dp1[i][0] %= mod
    
    for j in range(1,W):
        for i in range(H):
            dp0[i][j] = A[i][j] * B[i][j] % mod
            if i!=0:
                dp0[i][j] += A[i][j] * B[i][j] * dp1[i-1][j-1] % mod
                dp0[i][j] %= mod

            dp1[i][j] = (dp0[i][j] + dp1[i][j-1]) % mod
            if i!=0:
                dp1[i][j] += dp1[i-1][j]
                dp1[i][j] %= mod
    
    return dp1[H-1][W-1]

def solve_brute(H,W,A,B):
    

    res = 0
    for rS in range(1<<H):
        for cS in range(1<<W):
            R = [r for r in range(H) if rS>>r & 1]
            C = [c for c in range(W) if cS>>c & 1]

            if len(R)!=len(C) or len(R) == 0:
                continue

            GA = [[A[r][c] % mod for c in C] for r in R]
            GB = [[B[r][c] % mod for c in C] for r in R]
            res += det(GA) * det(GB)
            res %= mod
    
    return res

def solve_brute2(H,W,A,B):
    tB = [[B[i][j] for i in range(H)] for j in range(W)]
    C = mat_mul(A,tB)
    
    res = 0
    for S in range(1,1<<len(C)):
        RC = [i for i in range(len(C)) if S>>i & 1]
        G = [[C[i][j] for j in RC] for i in RC]
        res += det(G)
        res %= mod
    
    return res

def solve(H,W,A,B):
    tB = [[B[i][j] for i in range(H)] for j in range(W)]
    C = mat_mul(A,tB)
    for i in range(len(C)):
        j = i
        C[i][j] = (C[i][j] + 1) % mod
    
    return (det(C)-1) % mod

        

H,W = mi()
A = [li() for i in range(H)]
B = [li() for i in range(H)]

print(solve(H,W,A,B))
0