結果

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

ソースコード

diff # 

import sys
from math import gcd
from itertools import combinations

MOD = 90001

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

    # Function to compare N with 90001
    def compare_n_ge_90001(N_str):
        if len(N_str) > 5:
            return True
        elif len(N_str) ==5:
            return N_str >= '90001'
        else:
            return False

    if compare_n_ge_90001(N_str):
        print(0)
        return

    # Convert N to integer
    N = int(N_str)

    # Precompute factorial and inverse factorial modulo MOD
    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

    # Function to compute LCM of a list
    def lcm(a, b):
        return a * b // gcd(a, b)
    def compute_lcm(lst):
        res = 1
        for num in lst:
            res = lcm(res, num)
        return res

    # For each person, compute their G_i(x)
    # G_i(x) is a list where G_i[k] is the coefficient of x^k
    G = []
    for _ in range(M):
        k_i = int(input[ptr])
        ptr +=1
        A = list(map(int, input[ptr:ptr +k_i]))
        ptr +=k_i

        # Enumerate all non-empty subsets of A
        all_subsets = []
        for l in range(1, len(A)+1):
            for subset in combinations(A, l):
                all_subsets.append(subset)

        # Compute G_i(x)
        gi = [0]*(N+1)
        for subset in all_subsets:
            s = len(subset)
            d = compute_lcm(subset)
            sign = (-1) ** (s + 1)
            # For multiples of d: d*m <=N
            max_m = N // d
            for m in range(0, max_m +1):
                k = d * m
                coeff = sign * inv_fact[k]
                gi[k] = (gi[k] + coeff) % MOD

        G.append(gi)

    # Compute the product of all G_i
    # Initial product is [1] (all zeros except x^0)
    product = [0]*(N+1)
    product[0] = 1
    for gi in G:
        new_product = [0]*(N+1)
        for k1 in range(N+1):
            if product[k1] ==0:
                continue
            for k2 in range(N+1 -k1):
                if gi[k2] ==0:
                    continue
                k_total = k1 + k2
                if k_total > N:
                    continue
                new_product[k_total] = (new_product[k_total] + product[k1] * gi[k2]) % MOD
        product = new_product

    # Multiply by e^x's generating function
    # e^x is sum_{k=0}^N x^k /k! 
    ex = [inv_fact[k] for k in range(N+1)]
    new_product = [0]*(N+1)
    for k1 in range(N+1):
        if product[k1] ==0:
            continue
        for k2 in range(N+1 -k1):
            if ex[k2] ==0:
                continue
            k_total = k1 + k2
            if k_total > N:
                continue
            new_product[k_total] = (new_product[k_total] + product[k1] * ex[k2]) % MOD
    product = new_product

    # The coefficient of x^N is product[N]
    c = product[N]
    answer = (fact[N] * c) % MOD
    print(answer)

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