結果

問題 No.2807 Have Another Go (Easy)
ユーザー gew1fw
提出日時 2025-06-12 16:39:39
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,934 bytes
コンパイル時間 215 ms
コンパイル使用メモリ 82,580 KB
実行使用メモリ 53,404 KB
最終ジャッジ日時 2025-06-12 16:40:02
合計ジャッジ時間 4,717 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    M = int(input[idx]); idx +=1
    k = int(input[idx]); idx +=1
    C = list(map(int, input[idx:idx +k]))
    idx +=k
    
    # Precompute dp_total
    max_s = 2*N
    dp_total = [0] * (max_s)
    dp_total[0] = 1
    for s in range(1, max_s):
        for d in range(1,7):
            if s -d >=0:
                dp_total[s] = (dp_total[s] + dp_total[s -d]) % MOD
    
    # Compute T
    T = 0
    for s in range(max(0, max_s -6), max_s):
        if s >= max_s:
            continue
        required = max_s - s
        if required >6:
            cnt =0
        else:
            cnt = 6 - required +1
        T = (T + dp_total[s] * cnt) % MOD
    
    # Precompute for all C_i
    for ci in C:
        # Compute dp_bad
        dp_bad = [0] * (max_s)
        dp_bad[0] = 1
        for s in range(0, max_s):
            if dp_bad[s] ==0:
                continue
            m = s % N
            if m == ci:
                continue
            for d in range(1,7):
                s_new = s +d
                if s_new >= max_s:
                    # contributes to bad_sequences
                    pass
                else:
                    m_new = s_new % N
                    if m_new != ci:
                        dp_bad[s_new] = (dp_bad[s_new] + dp_bad[s]) % MOD
        
        # Compute bad_sequences
        bad = 0
        for s in range(max_s):
            if dp_bad[s] ==0:
                continue
            required = max_s - s
            if required <=0:
                continue
            if required >6:
                cnt =0
            else:
                cnt = 6 - required +1
            bad = (bad + dp_bad[s] * cnt) % MOD
        
        ans = (T - bad) % MOD
        if ans <0:
            ans += MOD
        print(ans)
    
if __name__ == "__main__":
    main()
0