結果

問題 No.2788 4-33 Hard
ユーザー flygon
提出日時 2024-06-15 01:26:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 158 ms / 2,000 ms
コード長 1,641 bytes
コンパイル時間 537 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 78,768 KB
最終ジャッジ日時 2024-06-15 01:26:35
合計ジャッジ時間 11,114 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 52
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(5*10**5)
input = sys.stdin.readline
from collections import defaultdict, deque, Counter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right
from math import gcd
mod = 998244353
O = [list(map(int,input().split())) for i in range(5)]
X = [list(map(int,input().split())) for i in range(5)]
all = []
for i in range(5):
    for j in range(34):
        all.append([i,j])

cnum = [[[1]*10 for i in range(34)] for i in range(5)]
for i in range(5):
    for j in range(34):
        for k in range(1,10):
            cnum[i][j][k] =cnum[i][j][k-1] * (O[i][j]-k+1) * pow(k, mod-2, mod) % mod
            cnum[i][j][k] %= mod
ord = [0]
divm = []
def div(tot):
    if tot == 8:
        divm.append(ord[::1])
        return
    for i in range(1,9):
        if i < ord[-1]: continue
        if tot + i > 8:break
        ord.append(i)
        div(tot + i)
        ord.pop()

div(0)
ans = 0
dp = [[[0]*34 for i in range(5)] for i in range(9)]
dp[0][0][0] = 1
for dx,dy in all:
    new = [[[0]*34 for i in range(5)] for i in range(9)]
    for lx,ly in all:
        for lcnt in range(0,9):
            new[lcnt][lx][ly] += dp[lcnt][lx][ly]
            new[lcnt][lx][ly] %= mod
            for cnt in range(1,9):
                if lx+dx*cnt > 4 or ly+dy*cnt > 33: continue
                if lcnt + cnt > 8:break
                if i >= 1:
                    new[lcnt+cnt][lx+dx*cnt][ly+dy*cnt] += dp[lcnt][lx][ly]*cnum[dx][dy][cnt]
                    new[lcnt+cnt][lx+dx*cnt][ly+dy*cnt] %= mod
    dp = new

for i in range(5):
    ans += dp[-1][4-i][33]*X[i][0]%mod
    ans %= mod
print(ans)
0