けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 185 C - Duodecim Ferra (灰色, 300 点)

AtCoder AtCoder300点 ABC-C 灰色diff 二項係数 数え上げ問題 重複組合せ 易しい数え上げ問題 数え上げ:組合せ 算数と数学

二項係数！！　オーバーフローがこわくて、漸化式で二項係数求めるやつをやった。でももっと簡単にできた。

問題概要

長さ L の鉄の棒が東西方向に横たわっています。

この棒を 11 箇所で切断して、12 本に分割します。このとき分割後の各棒の長さが全て正整数になるように分割しなければなりません。

分割のしかたが何通りあるかを求めてください。

制約

  • 12 \le L \le 200

考えたこと

下図は L = 14 の場合の一例を示している。

L = 14 の場合の一つ一つは次のように考えることができる。

  • 上図の「切り口になりうる箇所」 (黒太線で表した) は、全部で 13 箇所ある
  • そのうち 11 箇所を選べば、12 本に分割できる

つまり、13 箇所のうちの 11 箇所を選ぶ問題だということなので、 {}_{13}{\rm C}_{11} 通りとなる。

一般の長さ L の場合も同様に、

  • 切り口の候補は L-1 箇所
  • そのうちの 11 箇所を選べば良い

ということなので、答えは {}_{L-1}{\rm C}_{11} 通り。

計算

二項係数の計算をすればよいことがわかったのだが、オーバーフローが怖い。いくつか方法がある。

一番簡単なのは、

{}_{L-1}{\rm C}_{11} = \frac{(L-1) \times (L-2) \times \dots \times (L-11)}{1 \times 2 \times \dots \times 11}

を計算するときに、次のようにする方法。

res = 1;
for (int i = 1; i <= 11; ++i) {
    res *= (L - i);
    res /= i;
}

このとき res /= i のところで、割り切れないのに割ってしまうことはないのかと一瞬不安になるのだけど、そんなことはない。なぜなら

「連続する n 個の自然数の積は、かならず n! で割り切れる」

という性質があるからだ。というわけで、計算できた！

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long L;
    cin >> L;
    long long res = 1;
    for (int i = 1; i <= 11; ++i) {
        res *= L - i;
        res /= i;
    }
    cout << res << endl;
}