結果

問題 No.3376 Rectangle in Circle
コンテスト
ユーザー LyricalMaestro
提出日時 2026-05-25 01:38:40
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 353 ms / 2,000 ms
コード長 2,496 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 214 ms
コンパイル使用メモリ 84,828 KB
実行使用メモリ 146,428 KB
最終ジャッジ日時 2026-05-25 01:38:46
合計ジャッジ時間 4,693 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/3376


MOD = 998244353


def solve_case_all_black(N):
    dp = [0] * (N + 1)
    for i in reversed(range(N)):
        dp[i] = (N * pow(N - i, MOD - 2, MOD)) % MOD
        dp[i] += dp[i + 1]
        dp[i] %= MOD
    return dp[0]


def solve(N, L, D):
    if L % 2 != 0:
        return solve_case_all_black(N)

    d_map = {}
    for i in range(N):
        d = D[i]
        d_map[d] = i

    diameter_pair = 0    
    for i in range(N):
        d = D[i]
        d1 = (d + L // 2) % L

        if d1 in d_map:
            diameter_pair += 1
            del d_map[d]
            del d_map[d1]

    if diameter_pair <= 1:
        return solve_case_all_black(N)

    # 異なる4つが存在して
    rest_point = N - 2 * diameter_pair
    dp1 = [0] * diameter_pair
    dp1[diameter_pair - 1] = N * pow(N - (rest_point + diameter_pair + 1), MOD - 2, MOD)
    dp1[diameter_pair - 1] %= MOD
    
    for i in reversed(range(diameter_pair - 1)):
        dp1[i] = N * pow(N - (rest_point + i + 2), MOD - 2, MOD)
        dp1[i] %= MOD

        p = 2 * (diameter_pair - 1 - i)
        p %= MOD
        p *= pow(N - (rest_point + i + 2), MOD - 2, MOD)
        p %= MOD
        p *= dp1[i + 1]
        p %= MOD
        dp1[i] += p
        dp1[i] %= MOD

    dp0 = [0] * (diameter_pair + 1)
    dp0[diameter_pair] = N * pow(N - (rest_point + diameter_pair), MOD - 2, MOD)
    dp0[diameter_pair] %= MOD
    q = diameter_pair
    q %= MOD
    q *= pow(N - (rest_point + diameter_pair), MOD - 2, MOD)
    q %= MOD
    q *= dp1[diameter_pair - 1] 
    q %= MOD
    dp0[diameter_pair] += q
    dp0[diameter_pair] %= MOD
    for i in reversed(range(diameter_pair)):
        dp0[i] = N * pow(N - (rest_point + i), MOD - 2, MOD)
        dp0[i] %= MOD

        p = 2 * (diameter_pair - i)
        p %= MOD
        p *= pow(N - (rest_point + i), MOD - 2, MOD)
        p %= MOD
        p *= dp0[i + 1]
        p %= MOD
        dp0[i] += p
        dp0[i] %= MOD
            
        q = i
        q %= MOD
        q *= pow(N - (rest_point + i), MOD - 2, MOD)
        q %= MOD
        q *= dp1[i - 1] 
        q %= MOD
        dp0[i] += q
        dp0[i] %= MOD
    return dp0[0]



def main():
    T = int(input())
    answers = []
    for _ in range(T):
        N, L = map(int, input().split())
        D = list(map(int, input().split()))
        ans = solve(N, L, D)
        answers.append(ans)

    for ans in answers:
        print(ans)









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