[AtCoder] ABC 185 C – Duodecim Ferra

2020年12月13日

問題

方針

鉄の棒を \( 12 \) 本に分割したとき、棒 \( i \) の長さを \( l_i \) とすると、

\[ l_1 + l_2 + \cdots + l_{12} = L\]

となります。ここで、\( a_i \) を非負整数として、\( a_i = l_i – 1 \) とすると、

\[ a_1 + a_2 + \cdots + a_{12} = L – 12\]

となります。これは、非負整数解の個数を求める問題となるので、答えは

\[ {}_{L – 1} \mathrm{ C }_{11}\]

となります。

二項係数を求めるテクニックとして、

\[ {}_{n} \mathrm{ C }_{k} = \prod_{ i = 1 }^k \dfrac{n + 1 – i}{i}\]

となることを利用すると良いかもしれません。

コード

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

int main() {
    ll L;
    cin >> L;
    ll ans = 1;
    for (ll i = 1; i <= 11; i++) {
        ans *= (L - i);
        ans /= i;
    }
    cout << ans << "\n";
    return 0;
}