ABC185 C - Duodecim Ferra

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import numpy as np
from numpy import linalg as LA

# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    L = ii()
    print(comb(L-1, 11))


if __name__ == '__main__':
    main()

考え方

長さLのうち、11か所切断する。
長さがLの場合には、切断可能な個所はL-1箇所存在する。
そのため、L-1箇所から11か所の切断箇所を選択する。
これは「x個のうちy個を選ぶ」組み合わせの考え方なので、
組み合わせの公式を用いることで、回答することができる。

順列と組み合わせの公式とその違い【問題付き】 | 理系ラボ

問題の制約でLは最大でも200だが、
もっと大きくなる場合には、オーバーフローしないように気を付ける必要がある。