結果

問題 No.2825 Sum of Scores of Sets of Specified Sections
コンテスト
ユーザー chineristAC
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

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