結果

問題 No.3376 Rectangle in Circle
コンテスト
ユーザー 👑 loop0919
提出日時 2025-10-12 20:32:19
言語 PyPy3
(7.3.15)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,549 bytes
コンパイル時間 183 ms
コンパイル使用メモリ 82,764 KB
実行使用メモリ 848,976 KB
最終ジャッジ日時 2025-11-21 20:50:19
合計ジャッジ時間 4,643 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 RE * 6 MLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353
MAX_N = 5000

inv = [0] * (MAX_N + 1)
for i in range(1, MAX_N + 1):
    inv[i] = pow(i, -1, MOD)


def exp_all(N):
    exp = 0
    for i in range(1, N + 1):
        exp += N * inv[i] % MOD
        exp %= MOD

    return exp


def solve():
    N, L = [int(x) for x in input().split()]
    D = set([int(d) for d in input().split()])

    if L % 2 == 1:
        print(exp_all(N))
        return

    diameters = 0
    normals = 0

    for d in D:
        if (d + L // 2) % L in D:
            diameters += 1
        else:
            normals += 1

    diameters //= 2

    if diameters <= 1:
        print(exp_all(N))
        return

    dp = [[[0] * (normals + 1) for _ in range(diameters + 1)] for _ in range(3)]

    for i in range(1, -1, -1):
        for j in range(diameters, -1, -1):
            for k in range(normals, -1, -1):
                remain = N - i - j - k

                exp = (i + j + k) * inv[remain] % MOD

                if j > i:
                    exp += (dp[i + 1][j][k] + 1) * (j - i) % MOD * inv[remain] % MOD
                    exp %= MOD
                if j < diameters:
                    exp += (dp[i][j + 1][k] + 1) * 2 * (diameters - j) % MOD * inv[remain] % MOD
                    exp %= MOD
                if k < normals:
                    exp += (dp[i][j][k + 1] + 1) * (normals - k) % MOD * inv[remain] % MOD
                    exp %= MOD

                dp[i][j][k] = exp

    print(dp[0][0][0])


if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        solve()
0