ABC解説

【pythonでABC185を解説】C - Duodecim Ferra

問題概要

問題ページ

C - Duodecim Ferra
C - Duodecim Ferra

問題ページへ移動する

問題文

長さ \(L\) の鉄の棒が東西方向に横たわっています。この棒を \(11\) 箇所で切断して、\(12\) 本に分割します。このとき分割後の各棒の長さが全て正整数になるように分割しなければなりません。

分割のしかたが何通りあるかを求めてください。二つの分割の方法は、一方で分割されているが他方で分割されていない位置が存在する場合に、そしてその場合に限って区別されます。

なお、この問題の制約下で答えは \(2^{63}\) 未満であることが証明できます。

制約

  • \(12 \le L \le 200\)
  • \(L\) は整数

問題の考察

組み合わせの問題。

要素\(L\)を\(12\)個に分割する場合には、\(L\)個の要素の間\(L-1\)箇所から\(11\)（\(12-1\)）箇所選んで仕切りで仕切ると考えれば良い。

例題1は、\(L=12\)なので、\(11\)箇所から\(11\)箇所選んで仕切るので\({}_11 C_11\)\(=\)\({}_11 C_0\)となる。

例題3は、\(L=17\)なので、\(16\)箇所から\(11\)箇所選んで仕切るので\({}_16 C_11\)\(=\)\({}_16 C_5\)となる。

 

たびすけ
たびすけ
競プロでは組み合わせの問題は頻出なので考え方と計算方法を覚えましょう！
理解した後はライブラリ登録を忘れずに！
【python/アルゴリズム】競プロ頻出アルゴリズムライブラリ一覧

続きを見る

ACコード

import sys


def combination(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    else:
        denominator = 1
        for i in range(n, n - r, -1):
            denominator = (denominator * i)
        molecule = 1
        for i in range(1, r + 1):
            molecule = (molecule * i)
        return denominator // molecule


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    l = int(input().rstrip('\n'))
    print(combination(l - 1, 11))


if __name__ == '__main__':
    solve()

-ABC解説
-,