結果

問題 No.2136 Dice Calendar?
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:56:50
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,503 bytes
コンパイル時間 222 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 420,352 KB
最終ジャッジ日時 2025-06-12 21:00:50
合計ジャッジ時間 22,289 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

MOD = 998244353
max_n = 20

# Precompute factorials and inverse factorials modulo MOD
fact = [1] * (max_n + 1)
for i in range(1, max_n + 1):
    fact[i] = fact[i-1] * i % MOD

inv_fact = [1] * (max_n + 1)
inv_fact[max_n] = pow(fact[max_n], MOD - 2, MOD)
for i in range(max_n - 1, -1, -1):
    inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    dice = []
    for _ in range(N):
        s = list(map(int, input[ptr:ptr+6]))
        ptr += 6
        dice.append(s)
    
    # Initialize DP with the zero state
    dp = set()
    initial_state = tuple([0]*9)
    dp.add(initial_state)
    
    for die in dice:
        new_dp = set()
        for state in dp:
            for d in die:
                new_state = list(state)
                new_state[d-1] += 1
                new_state_tuple = tuple(new_state)
                new_dp.add(new_state_tuple)
        dp = new_dp
        if not dp:
            break
    
    total = 0
    for state in dp:
        sum_counts = sum(state)
        if sum_counts != N:
            continue
        numerator = fact[N]
        denominator = 1
        for cnt in state:
            if cnt > 0:
                denominator = denominator * fact[cnt] % MOD
        inv_denominator = pow(denominator, MOD - 2, MOD)
        term = numerator * inv_denominator % MOD
        total = (total + term) % MOD
    print(total)

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