結果

問題 No.2807 Have Another Go (Easy)
ユーザー lam6er
提出日時 2025-04-16 15:59:40
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,157 bytes
コンパイル時間 567 ms
コンパイル使用メモリ 81,928 KB
実行使用メモリ 53,360 KB
最終ジャッジ日時 2025-04-16 16:03:05
合計ジャッジ時間 4,914 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    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
    C = list(map(int, input[ptr:ptr + k]))
    ptr += k
    
    max_x = 2 * N - 1
    ways = [0] * (max_x + 1)
    ways[0] = 1
    prefix = [0] * (max_x + 2)
    prefix[0] = 0
    prefix[1] = ways[0]
    
    for x in range(1, max_x + 1):
        l = max(0, x - 6)
        r = x - 1
        if l == 0:
            sum_ways = prefix[r + 1] - prefix[l]
        else:
            sum_ways = (prefix[r + 1] - prefix[l]) % MOD
        ways[x] = sum_ways % MOD
        prefix[x + 1] = (prefix[x] + ways[x]) % MOD
    
    T = 0
    for x in range(max(0, 2 * N - 6), 2 * N):
        d_min = 2 * N - x
        if d_min < 1:
            cnt = 6
        else:
            cnt = max(0, 6 - d_min + 1)
        if cnt <= 0:
            continue
        T = (T + ways[x] * cnt) % MOD
    
    for c in C:
        r_i = c % N
        avoid = [0] * (max_x + 1)
        if 0 % N != r_i:
            avoid[0] = 1
        else:
            avoid[0] = 0
        avoid_prefix = [0] * (max_x + 2)
        avoid_prefix[1] = avoid[0]
        
        for x in range(1, max_x + 1):
            if x % N == r_i:
                avoid[x] = 0
                avoid_prefix[x + 1] = avoid_prefix[x]
                continue
            l = max(0, x - 6)
            r = x - 1
            if l == 0:
                sum_av = (avoid_prefix[r + 1] - avoid_prefix[l]) % MOD
            else:
                sum_av = (avoid_prefix[r + 1] - avoid_prefix[l]) % MOD
            avoid[x] = sum_av % MOD
            avoid_prefix[x + 1] = (avoid_prefix[x] + avoid[x]) % MOD
        
        S_i = 0
        for x in range(max(0, 2 * N - 6), 2 * N):
            d_min = 2 * N - x
            if d_min < 1:
                cnt = 6
            else:
                cnt = max(0, 6 - d_min + 1)
            if cnt <= 0:
                continue
            S_i = (S_i + avoid[x] * cnt) % MOD
        
        ans = (T - S_i) % MOD
        print(ans)
        
if __name__ == '__main__':
    main()
0