結果

問題 No.3376 Rectangle in Circle
コンテスト
ユーザー lif4635
提出日時 2025-10-29 12:43:27
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,115 bytes
コンパイル時間 169 ms
コンパイル使用メモリ 82,656 KB
実行使用メモリ 86,216 KB
最終ジャッジ日時 2025-11-21 20:52:01
合計ジャッジ時間 4,656 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
mod = 998244353

class Comb:
    __slots__ = ["fac", "finv", "mod"]
    def __init__(self, lim:int, mod:int = mod):
        """
        mod : prime
        """
        self.fac = [1]*(lim+1)
        self.finv = [1]*(lim+1)
        self.mod = mod
        for i in range(2,lim+1):
            self.fac[i] = self.fac[i-1]*i%self.mod
        self.finv[lim] = pow(self.fac[lim],-1,mod)
        for i in range(lim,2,-1):
            self.finv[i-1] = self.finv[i]*i%self.mod
    
    def C(self, a, b):
        if b < 0 or a < b: return 0
        if a < 0: return 0
        return self.fac[a]*self.finv[b]%self.mod*self.finv[a-b]%self.mod
    
    def __call__(self, a, b):
        if b < 0 or a < b: return 0
        if a < 0: return 0
        return self.fac[a]*self.finv[b]%self.mod*self.finv[a-b]%self.mod
    
    def P(self, a, b):
        if b < 0 or a < b: return 0
        if a < 0: return 0
        return self.fac[a]*self.finv[a-b]%self.mod
    
    def H(self, a, b): return self.C(a+b-1,b)
    def F(self, a): return self.fac[a]
    def Fi(self, a): return self.finv[a]

lim = 5010
comb = Comb(lim)

p2 = [1] * (lim + 1)
for i in range(lim):
    p2[i+1] = 2 * p2[i] % mod

def solve():
    n, l = map(int, input().split())
    d = list(map(int, input().split()))
    if l & 1:
        ans = 0
        for i in range(n):
            ans += pow(n - i, -1, mod)
            ans %= mod
        print(n * ans % mod)
        return

    h = l // 2
    c = defaultdict(int)
    for x in d:
        c[x%h] += 1
    c = [*c.values()]
    c1 = c.count(1)
    c2 = c.count(2)

    ans = 0
    for p in range(n):
        tmp = 0
        for q in range(0, p+1):
            t1 = comb.P(c1, p-q) * comb.P(c2, q) % mod * p2[q] % mod
            tmp %= mod
            t1 += comb.P(c1, p-q) * q * (q - 1) * c2 % mod * comb.P(c2-1, q-2) % mod * p2[q-2] % mod
            tmp += t1 * comb(p, q) % mod
        ans += tmp * comb.F(n-p) % mod * n % mod * pow(n - p, -1, mod) % mod
        ans %= mod

    print(ans * comb.Fi(n) % mod)
    return

t = int(input())
for i in range(t):
    solve()
0