トヨタ自動車プログラミングコンテスト2025（AtCoder Beginner Contest 389）E,F,G 問題メモ

def solve(n, m, ppp):
    l = 0
    r = 1 << 50
    while l + 1 < r:
        mid = (l + r) // 2
        total = 0
        for p in ppp:
            k = (mid + p) // (2 * p)
            total += p * k * k
        if total <= m:
            l = mid
        else:
            r = mid

    ans = 0
    total = 0
    for p in ppp:
        k = (l + p) // (2 * p)
        ans += k
        total += p * k * k
    ans += (m - total) // (l + 1)
    return ans


n, m = map(int, input().split())
ppp = list(map(int, input().split()))
ans = solve(n, m, ppp)
print(ans)

from operator import add

from atcoder.lazysegtree import LazySegTree


def solve(n, contests, q, queries):
    lst = LazySegTree(max, -1, add, add, 0, list(range(500001)))
    for l, r in contests:
        s = lst.max_right(0, lambda x: x < l)
        t = lst.max_right(0, lambda x: x <= r)
        lst.apply(s, t, 1)
    ans = []
    for x in queries:
        ans.append(lst.get(x))
    return ans


n = int(input())
contests = [tuple(map(int, input().split())) for _ in range(n)]
q = int(input())
queries = [int(input()) for _ in range(q)]
ans = solve(n, contests, q, queries)
print('\n'.join(map(str, ans)))

import os
import sys

import numpy as np


def solve(n, p):
    def mod_pow(x, a, MOD):
        ret = 1
        cur = x
        while a > 0:
            if a & 1:
                ret = ret * cur % MOD
            cur = cur * cur % MOD
            a >>= 1
        return ret

    def prepare_factorials(n, MOD):
        factorials = np.ones(n + 1, np.int64)
        for m in range(1, n + 1):
            factorials[m] = factorials[m - 1] * m % MOD
        inversions = np.ones(n + 1, np.int64)
        inversions[n] = mod_pow(factorials[n], MOD - 2, MOD)
        for m in range(n, 1, -1):
            inversions[m - 1] = inversions[m] * m % MOD
        return factorials, inversions

    def simple_convolution(aaa, bbb, MOD):
        n = aaa.size
        m = bbb.size
        result = np.zeros(n + m - 1, np.int64)
        for i in range(n):
            for j in range(m):
                result[i + j] += aaa[i] * bbb[j]
                result[i + j] %= MOD
        return result

    facts, finvs = prepare_factorials(n * n, p)
    l_lim = n // 2
    e_lim = n * (n - 1) // 2

    pre = np.zeros((l_lim + 1, l_lim + 1, e_lim * e_lim * 2), np.int64)
    for k in range(1, l_lim + 1):
        aaa = np.zeros(k + 1, np.int64)
        for i in range(1, k + 1):
            aaa[i] = facts[k] * finvs[i] % p * finvs[k - i] % p
        bbb = aaa.copy()
        pre[k, 1, :k + 1] = aaa
        for c in range(2, l_lim + 1):
            bbb = simple_convolution(aaa, bbb, p)
            edges = c * (c - 1) // 2
            ccc = np.zeros(edges + 1, np.int64)
            for i in range(edges + 1):
                ccc[i] = facts[edges] * finvs[i] % p * finvs[edges - i] % p
            ddd = simple_convolution(bbb, ccc, p)
            pre[k, c, :ddd.size] = ddd

    dp = np.zeros((n + 1, l_lim + 1, e_lim + 1, l_lim + 1, 2), np.int64)
    # [今までで使った頂点数, そのうち距離偶数の頂点数, 辺数, 直近で追加した層の頂点数, 直近で追加した層が偶数か奇数か]
    dp[1, 1, 0, 1, 0] = 1
    for v in range(1, n):
        for l in range(1, l_lim + 1):
            for e in range(e_lim):
                for u in range(1, l_lim + 1):
                    if dp[v, l, e, u, 0] > 0:
                        t = dp[v, l, e, u, 0]
                        r = v - l
                        for ar in range(1, l_lim - r + 1):
                            t2 = t * facts[n - v] % p * finvs[ar] % p * finvs[n - v - ar] % p
                            for ae in range(ar, e_lim - e + 1):
                                dp[v + ar, l, e + ae, ar, 1] += t2 * pre[u, ar, ae]
                                dp[v + ar, l, e + ae, ar, 1] %= p
                    if dp[v, l, e, u, 1] > 0:
                        t = dp[v, l, e, u, 1]
                        for al in range(1, l_lim - l + 1):
                            t2 = t * facts[n - v] % p * finvs[al] % p * finvs[n - v - al] % p
                            for ae in range(al, e_lim - e + 1):
                                dp[v + al, l + al, e + ae, al, 0] += t2 * pre[u, al, ae]
                                dp[v + al, l + al, e + ae, al, 0] %= p
    ans = np.zeros(e_lim + 1, np.int64)
    for e in range(n - 1, e_lim + 1):
        ans[e] = dp[n, l_lim, e].sum() % p
    return ans[n - 1:]


SIGNATURE = '(i8,i8)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

n, p = map(int, input().split())
ans = solve(n, p)
print(*ans)