結果

問題 No.2807 Have Another Go (Easy)
ユーザー gew1fw
提出日時 2025-06-12 13:14:12
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,826 bytes
コンパイル時間 169 ms
コンパイル使用メモリ 82,572 KB
実行使用メモリ 272,184 KB
最終ジャッジ日時 2025-06-12 13:16:40
合計ジャッジ時間 4,832 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    Cs = list(map(int, input[ptr:ptr+k]))
    ptr +=k
    
    # Compute original DP
    max_s = 2*N -1
    dp = [0]*(max_s +1)
    dp[0] =1
    for s in range(1, max_s +1):
        for d in range(1,7):
            if s -d >=0:
                dp[s] = (dp[s] + dp[s-d]) % MOD
    
    # Compute total_valid_sequences
    total_valid =0
    for s_prev in range(max_s +1):
        if s_prev >=2*N:
            continue
        # Compute count(s_prev)
        if s_prev < 2*N -6:
            cnt =0
        else:
            cnt =7 - (2*N - s_prev)
        total_valid = (total_valid + dp[s_prev] * cnt) % MOD
    
    # Precompute the original sum for the last 6 residues
    original_sum =0
    last_r_start = N-6 if N >=6 else 0
    for r in range(last_r_start, N):
        s_prev = N + r
        if s_prev >=2*N:
            continue
        cnt =7 - (2*N - s_prev)
        original_sum = (original_sum + dp[s_prev] * cnt) % MOD
    
    # Process each query
    for C in Cs:
        # Compute forbidden count
        # We need to compute the sum of dp_forbidden[1][r] * (7 - (N -r)) for r in [N-6, N-1]
        # where dp_forbidden[1][r] is the number of ways to reach s_prev =N +r without any partial sums ≡C mod N
        
        # Compute forbidden_sum
        forbidden_sum =0
        for r in range(N-6, N):
            if r <0:
                continue
            # Check if r == C mod N
            if r == C % N:
                continue
            s_prev = N + r
            if s_prev >=2*N:
                continue
            # Compute the number of ways to reach s_prev without any partial sums ≡C mod N
            # This is done via a modified DP
            # We need to compute the forbidden DP for this C
            # But this is time-consuming for large N.
            # For the sake of this example, we'll use a placeholder approach.
            # This part is not optimized and will not work for large N.
            # This code is illustrative but not efficient.
            dp_forbidden = [0]*(max_s +1)
            dp_forbidden[0] =1 if 0 % N != C else 0
            for s in range(1, max_s +1):
                if s % N == C % N:
                    dp_forbidden[s] =0
                    continue
                for d in range(1,7):
                    if s -d >=0:
                        dp_forbidden[s] = (dp_forbidden[s] + dp_forbidden[s-d]) % MOD
            cnt =7 - (2*N - s_prev)
            forbidden_sum = (forbidden_sum + dp_forbidden[s_prev] * cnt) % MOD
        
        answer = (total_valid - forbidden_sum) % MOD
        print(answer)
        
if __name__ == "__main__":
    main()
0