Neterukun's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Neterukun1993/Library

:heavy_check_mark: 写像12相
(Combination/twelvefold_way.py)

概要

ボールを箱に入れるときの場合の数を考える。このとき、ボールの区別 / 箱の区別 / 入れ方の制約 によって12パターンの数え方が存在する。

ボール 箱 入れ方に制約なし 箱の中身は１個以下 箱の中身は１個以上
区別できる 区別できる way1 way2 way3
区別できない 区別できる way4 way5 way6
区別できる 区別できない way7 way8 way9
区別できない 区別できない way10 way11 way12

上図は AOJ Balls and Boxes 1 からの出典

使い方

way1(ball: int, box: int) -> int
ボールの個数 ball と箱の個数 box に対して、way1 での場合の数を返す。

way2 から way12 まで同様の方法で使うことができる。ただし、コンテスト中にそのままペタリすることはあまりなく、数え上げ問題で状況整理したいときの確認で使うことが大半かも。

Depends on

Verified with

Code

from Combination.modinv_combination import Combination


MOD = 10 ** 9 + 7
comb = Combination(10 ** 6 + 10, MOD)


def way1(ball, box):
    """ball: True / box: True / constraints: None
    -> ans = box ** ball
    """
    ans = pow(box, ball, MOD)
    return ans


def way2(ball, box):
    """ball: True / box: True / constraints: 1 or less
    -> ans = perm(box, ball)
    """
    if ball > box:
        return 0
    return comb.perm(box, ball)


def way3(ball, box):
    """ball: True / box: True / constraints: 1 or more
    -> ans = (包除原理)
    """
    if ball < box:
        return 0
    ans = 0
    for i in range(box + 1):
        ans += (pow(-1, i, MOD) * comb.comb(box, i) % MOD) * pow(box - i, ball, MOD)
        ans %= MOD
    return ans


def way4(ball, box):
    """ball: False / box: True / constraints: None
    -> ans = comb(box + ball - 1, ball)
    """
    return comb.comb(ball + box - 1, ball)

    # 区別するbox個の箱 -> 区別しない(box - 1)個の仕切に変換して解く


def way5(ball, box):
    """ball: False / box: True / constraints: 1 or less
    -> ans = comb(box, ball)
    """
    if ball > box:
        return 0
    return comb.comb(box, ball)


def way6(ball, box):
    """ball: False / box: True / constraints: 1 or more
    -> ans = combination(ball - 1, box - 1)
    """
    if ball < box:
        return 0
    return comb.comb(ball - 1, box - 1)

    # 考え方1
    # ボールを一列に並べたとき、(ball - 1)箇所ある隙間から、(box - 1)個を選ぶ

    # 考え方2
    # あらかじめ、すべての箱にボールを1つずつ配っておくと、
    # 区別しない(ball - box)個のボールを、区別するbox個の箱に配る通り数に帰着
    # -> way4(ball - box, box) と同等の問題となる


def way7(ball, box):
    """ball: True / box: False / constraints: None
    -> ans = B(ball, box) Bはベル数 / 計算量 O(ball * box)
    """
    # B[i][j] := S[i][j] + S[i][j - 1] + ... + S[i][0]
    # S[i][j] := i個(区別する)をkグループ(区別しない)に分ける場合の数
    S = [[0] * (box + 1) for i in range(ball + 1)]
    S[0][0] = 1
    for i in range(ball):
        for j in range(box):
            S[i + 1][j + 1] = S[i][j] + S[i][j + 1] * (j + 1)
            S[i + 1][j + 1] %= MOD
    B_ij = sum(S[ball][0:box + 1]) % MOD
    return B_ij


def way8(ball, box):
    """ball: True / box: False / constraints: 1 or less
    -> ans = int(ボールの数 <= 箱の数)
    """
    return int(ball <= box)


def way9(ball, box):
    """ball: True / box: False / constraints: 1 or more
    -> ans = S(ball, box) Sはスターリング数 / 計算量 O(ball * box)
    """
    if ball < box:
        return 0

    # S[i][j] := i個(区別する)をkグループ(区別しない)に分ける場合の数
    S = [[0] * (box + 1) for i in range(ball + 1)]
    S[0][0] = 1
    for i in range(ball):
        for j in range(box):
            S[i + 1][j + 1] = S[i][j] + S[i][j + 1] * (j + 1)
            S[i + 1][j + 1] %= MOD
    return S[ball][box]


def way10(ball, box):
    """ball: False / box: False / constraints: None
    ans = P(ball, box) Pは分割数 / 計算量 O(ball * box)
    """
    # P[i][j] := 整数iを順序を区別せずに「j以下の自然数」の和に分ける場合の数
    P = [[0] * (ball + 1) for _ in range(ball + 1)]
    for j in range(ball + 1):
        P[0][j] = 1
    for i in range(ball):
        for j in range(ball):
            if i - j >= 0:
                P[i + 1][j + 1] = (P[i + 1][j] + P[i - j][j + 1]) % MOD
            else:
                P[i + 1][j + 1] = P[i + 1][j]
    return P[ball][min(box, ball)]


def way11(ball, box):
    """ball: False / box: False / constraints: 1 or less
    -> ans = int(ボールの数 <= 箱の数)
    """
    return int(ball <= box)


def way12(ball, box):
    """ball: False / box: False / constraints: 1 or more
    ans = P(ball - box, box) Pは分割数 / 計算量 O(ball * box)
    """
    if ball < box:
        return 0

    # P[i][j] := 整数iを順序を区別せずに「j以下の自然数」の和に分ける場合の数
    diff = ball - box
    P = [[0] * (diff + 1) for _ in range(diff + 1)]
    for j in range(diff + 1):
        P[0][j] = 1
    for i in range(diff):
        for j in range(diff):
            if i - j >= 0:
                P[i + 1][j + 1] = (P[i + 1][j] + P[i - j][j + 1]) % MOD
            else:
                P[i + 1][j + 1] = P[i + 1][j]
    return P[diff][min(diff, box)]

    # あらかじめ、すべての箱にボールを1つずつ配っておくと
    # 区別しない(ball - box)個のボールを、区別しないbox個の箱に配る通り数に帰着
    # -> way11(ball - box, box) と同等の問題となる
Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError
Back to top page