結果

問題 No.1763 Many Balls
ユーザー lam6er
提出日時 2025-04-09 21:02:54
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,180 bytes
コンパイル時間 261 ms
コンパイル使用メモリ 82,840 KB
実行使用メモリ 94,184 KB
最終ジャッジ日時 2025-04-09 21:04:34
合計ジャッジ時間 12,653 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 WA * 4 TLE * 1 -- * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 90001

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N_str = input[ptr]
    ptr += 1
    M = int(input[ptr])
    ptr += 1
    
    if len(N_str) > 5:
        print(0)
        return
    N = int(N_str)
    if N >= MOD:
        print(0)
        return
    n = N
    
    # Read M persons' conditions
    persons = []
    for _ in range(M):
        k_i = int(input[ptr])
        ptr +=1
        A = list(map(int, input[ptr:ptr +k_i]))
        ptr += k_i
        persons.append(A)
    
    # Precompute fact and inv_fact up to n
    max_n = n
    fact = [1] * (max_n +1)
    for i in range(1, max_n +1):
        fact[i] = fact[i-1] * i % MOD
    
    inv_fact = [1] * (max_n +1)
    inv_fact[max_n] = pow(fact[max_n], MOD-2, MOD)
    for i in range(max_n-1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
    
    # Precompute allowed counts for each person
    allowed = []
    for person in persons:
        A_list = person
        allowed_i = [False]*(n+1)
        for c in range(n+1):
            for a in A_list:
                if c % a == 0:
                    allowed_i[c] = True
                    break
        allowed.append(allowed_i)
    
    # Initialize DP: current possible sums and their coefficients
    dp = [0]*(n+1)
    dp[0] = 1
    
    for person_idx in range(M):
        allowed_i = allowed[person_idx]
        new_dp = [0]*(n+1)
        for s in range(n+1):
            if dp[s] ==0:
                continue
            for c in range(n+1):
                if not allowed_i[c]:
                    continue
                if s + c > n:
                    continue
                term = dp[s] * inv_fact[c] % MOD
                new_dp[s + c] = (new_dp[s + c] + term) % MOD
        dp = new_dp
    
    # Compute e^x's terms (inv_fact[d] for d in 0..n)
    e_terms = [inv_fact[d] for d in range(n+1)]
    
    # Compute result = sum (dp[s] * e_terms[d]) where s + d =n
    res = 0
    for s in range(n+1):
        d = n - s
        if d <0:
            continue
        res = (res + dp[s] * e_terms[d]) % MOD
    
    res = res * fact[n] % MOD
    print(res)
    
if __name__ == '__main__':
    main()
0