結果

問題 No.1763 Many Balls
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:41:36
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,482 bytes
コンパイル時間 218 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 72,192 KB
最終ジャッジ日時 2025-06-12 20:41:51
合計ジャッジ時間 13,332 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 WA * 4 TLE * 1 -- * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 90001

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1

    if N >= MOD:
        print(0)
        return

    # Precompute factorial and inverse factorial mod MOD
    factorial = [1] * (MOD)
    for i in range(1, MOD):
        factorial[i] = factorial[i-1] * i % MOD

    inv_fact = [1] * (MOD)
    inv_fact[MOD-1] = pow(factorial[MOD-1], MOD-2, MOD)
    for i in range(MOD-2, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD

    # Read each person's conditions
    conditions = []
    for _ in range(M):
        k = int(input[ptr])
        ptr +=1
        A = list(map(int, input[ptr:ptr+k]))
        ptr +=k
        conditions.append(A)

    # Precompute for each person the allowed s
    allowed = []
    for A in conditions:
        is_allowed = [False] * (N +1)
        for s in range(0, N+1):
            for d in A:
                if d ==0:
                    continue
                if s % d ==0:
                    is_allowed[s] = True
                    break
        allowed.append(is_allowed)

    # Function to create the polynomial for a person
    def make_poly(allow):
        poly = [0]*(N+1)
        for s in range(0, N+1):
            if allow[s]:
                poly[s] = inv_fact[s]
            else:
                poly[s] = 0
        return poly

    # Initialize E as 1 (only x^0 term)
    E = [0]*(N+1)
    E[0] = 1

    # Multiply by each person's polynomial
    for i in range(M):
        person_poly = make_poly(allowed[i])
        new_E = [0]*(N+1)
        for a in range(0, N+1):
            if E[a] ==0:
                continue
            for b in range(0, N -a +1):
                if person_poly[b] ==0:
                    continue
                new_E[a + b] = (new_E[a + b] + E[a] * person_poly[b]) % MOD
        E = new_E

    # Prepare e^x polynomial: coefficients are inv_fact[s]
    e_poly = [inv_fact[s] for s in range(N+1)]

    # Multiply E with e_poly
    result_poly = [0]*(N+1)
    for a in range(0, N+1):
        if E[a] ==0:
            continue
        for b in range(0, N -a +1):
            term = E[a] * e_poly[b] % MOD
            result_poly[a + b] = (result_poly[a + b] + term) % MOD

    # The coefficient at x^N
    coeff = result_poly[N]

    # Compute N! mod MOD
    n_fact = factorial[N]

    # Total ways
    total = (n_fact * coeff) % MOD

    print(total)

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