結果

問題 No.2807 Have Another Go (Easy)
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:51:15
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,669 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,646 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 312,428 KB
最終ジャッジ日時 2025-03-26 15:52:11
合計ジャッジ時間 5,442 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
MOD = 998244353

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr]); ptr +=1
    M = int(input[ptr]); ptr +=1
    k = int(input[ptr]); ptr +=1
    Cs = list(map(int, input[ptr:ptr+k]))
    ptr +=k
    
    max_sum = 2*N -1
    dp = [0]*(max_sum +1)
    dp[0] = 1
    for s in range(1, max_sum +1):
        for d in range(1,7):
            if s -d >=0:
                dp[s] = (dp[s] + dp[s-d]) % MOD
    
    total =0
    for s in range(max(0, 2*N -6), 2*N):
        cnt = dp[s]
        mul = (s +7 -2*N) 
        total = (total + cnt * mul) % MOD
    
    pow6 = [1]*(2*N +7)
    for i in range(1, 2*N +7):
        pow6[i] = (pow6[i-1] *6) % MOD
    
    for C in Cs:
        C_mod = C % N
        
        forbidden = [[0]*2 for _ in range(N)]
        if 0 != C_mod:
            forbidden[0][0] =1
        
        for s in range(0, 2*N):
            for a in 0,1:
                m = s - a*N
                if not (0 <= m < N):
                    continue
                if forbidden[m][a] ==0:
                    continue
                current = forbidden[m][a]
                for d in range(1,7):
                    new_s = a*N +m +d
                    if new_s >= 2*N:
                        pass
                    else:
                        if a ==0:
                            if new_s < N:
                                new_a =0
                                new_m = new_s
                            else:
                                new_a =1
                                new_m = new_s -N
                        else:
                            new_s_val = N +m +d
                            if new_s_val >=2*N:
                                continue
                            else:
                                new_a =1
                                new_m = m +d
                        if new_m == C_mod:
                            continue
                        if new_m >=N:
                            continue
                        forbidden[new_m][new_a] = (forbidden[new_m][new_a] + current) % MOD
        
        forbidden_count =0
        for s in range(2*N -6, 2*N):
            if s >=2*N:
                continue
            if s <0:
                continue
            a = 1
            m = s -N
            if m <0 or m >=N:
                continue
            mul = (s +7 -2*N)
            if m == C_mod:
                continue
            cnt = forbidden[m][1]
            forbidden_count = (forbidden_count + cnt * mul) % MOD
        
        ans = (total - forbidden_count) % MOD
        print(ans)
        
if __name__ == '__main__':
    main()
0