エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202）D,E,F問題メモ

def prepare(n):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m
        factorials.append(f)
    return factorials


def solve(a, b, k):
    if a == 0:
        assert k == 1
        return 'b' * b
    if b == 0:
        assert k == 1
        return 'a' * a

    starts_a = facts[a + b - 1] // facts[a - 1] // facts[b]
    if starts_a >= k:
        return 'a' + solve(a - 1, b, k)
    else:
        return 'b' + solve(a, b - 1, k - starts_a)


a, b, k = map(int, input().split())
facts = prepare(a + b)
print(solve(a, b, k))

import sys
from collections import defaultdict

sys.setrecursionlimit(300000)


def dfs(v, d):
    result = defaultdict(int)
    result[d] = 1
    for u in links[v]:
        ret = dfs(u, d + 1)
        if len(result) < len(ret):
            result, ret = ret, result
        for cd, cnt in ret.items():
            result[cd] += cnt
    for i, qd in queries[v]:
        ans[i] = result[qd] if qd in result else 0

    return result


input = sys.stdin.buffer.readline
n = int(input())
ppp = list(map(int, input().split()))
links = [set() for _ in range(n)]
for i, p in enumerate(ppp, start=1):
    links[p - 1].add(i)

queries = [set() for _ in range(n)]
q = int(input())
for i in range(q):
    u, d = map(int, input().split())
    u -= 1
    queries[u].add((i, d))
ans = [0] * q

dfs(0, 0)

print(*ans)

import os
import sys

import numpy as np


def solve(n, xys):
    MOD = 10 ** 9 + 7

    def dot(a, b):
        return (a.conjugate() * b).real

    def cross(a, b):
        return (a.conjugate() * b).imag

    def ccw(a, b, c):
        b -= a
        c -= a
        cbc = cross(b, c)
        if cbc > 0:
            return 1
        if cbc < 0:
            return -1
        if dot(b, c) < 0:
            return 2
        if abs(b) < abs(c):
            return -2
        return 0

    def count_between(n, xys):
        lower = np.zeros((n, n), np.int64)
        upper = np.zeros((n, n), np.int64)
        ccw_precalc = np.zeros((n, n, n), np.int8)
        for i in range(n - 2):
            p1 = xys[i]
            for k in range(i + 2, n):
                p3 = xys[k]
                lo = 0
                hi = 0
                for j in range(i + 1, k):
                    p2 = xys[j]
                    ccw_precalc[i, j, k] = cur_ccw = int(ccw(p1, p2, p3) < 0)
                    if cur_ccw:
                        hi += 1
                    else:
                        lo += 1
                lower[i, k] = lo
                upper[i, k] = hi

        return lower, upper, ccw_precalc

    lower, upper, ccw_precalc = count_between(n, xys)

    area_precalc = np.zeros((n, n), np.int8)
    for i in range(n - 1):
        p1 = xys[i]
        for j in range(i + 1, n):
            p2 = xys[j]
            area_precalc[i, j] = (p2.real + p1.real) * (p2.imag - p1.imag) % 2

    pow_precalc = np.zeros(n + n, np.int64)
    pow_precalc[0] = 1
    for i in range(1, n + n):
        pow_precalc[i] = pow_precalc[i - 1] * 2 % MOD

    ans = 0

    for i in range(n - 2):
        dp = np.zeros((2, 2, n, n, n), np.int64)
        for j in range(i + 1, n):
            lo = lower[i, j]
            hi = upper[i, j]
            area = area_precalc[i, j]
            dp[0, area, i, j, hi] = 1
            dp[1, area, i, j, lo] = 1

        for j in range(i, n - 2):
            for k in range(j + 1, n - 1):
                for l in range(k + 1, n):
                    c_ccw = ccw_precalc[j, k, l]
                    area = area_precalc[k, l]
                    if c_ccw:
                        lohi = lower[k, l]
                    else:
                        lohi = upper[k, l]
                    for m in range(lohi, l - 1):
                        dp[c_ccw, 0, k, l, m] = (dp[c_ccw, 0, k, l, m] + dp[c_ccw, area, j, k, m - lohi]) % MOD
                        dp[c_ccw, 1, k, l, m] = (dp[c_ccw, 1, k, l, m] + dp[c_ccw, area ^ 1, j, k, m - lohi]) % MOD

        for k in range(i + 2, n):
            lo_evn = np.zeros(k - i, np.int64)
            lo_odd = np.zeros(k - i, np.int64)
            hi_evn = np.zeros(k - i, np.int64)
            hi_odd = np.zeros(k - i, np.int64)
            for j in range(i, k):
                for m in range(k - i):
                    lo_evn[m] += dp[0, 0, j, k, m]
                    lo_odd[m] += dp[0, 1, j, k, m]
                    hi_evn[m] += dp[1, 0, j, k, m]
                    hi_odd[m] += dp[1, 1, j, k, m]

            bwd = k - i - 1

            for m1 in range(k - i):
                if lo_evn[m1] == 0:
                    continue
                for m2 in range(bwd - m1, k - i):
                    if hi_evn[m2] == 0:
                        continue
                    ans = (ans + lo_evn[m1] * hi_evn[m2] % MOD * pow_precalc[m1 + m2 - bwd]) % MOD

            for m1 in range(k - i):
                if lo_odd[m1] == 0:
                    continue
                for m2 in range(bwd - m1, k - i):
                    if hi_odd[m2] == 0:
                        continue
                    ans = (ans + lo_odd[m1] * hi_odd[m2] % MOD * pow_precalc[m1 + m2 - bwd]) % MOD

            ans = (ans - 1) % MOD

    return ans


SIGNATURE = '(i8,c16[:])'
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 = int(input())
xys = list(tuple(map(int, input().split())) for _ in range(n))
xys.sort()
xys = np.array([x + 1j * y for x, y in xys])
ans = solve(n, xys)
print(ans)