[AtCoder] ABC 178 D – Redistribution
問題
方針
非負整数解の個数
非負整数 \( x, y, z \) が
\[ x + y + z = n \]
を満たすとき、\( x, y, z \) の組み合わせは、\( {}_{n} \mathrm{ H }_{2} = {}_{n + 1} \mathrm{ C }_{2} \) となります。これは重複組み合わせの内容です。
問題に当てはめる
\( a_i \geq 3 \) を満たす整数が、
\[ a_1 + a_2 + \cdots + a_n = S \]
となる \( a_i \) の組み合わせは、
\( b_i \) を非負整数として、次の方程式を考えることと同じです。
\[ b_1 + b_2 + \cdots + b_n = S – 3n\]
上記を満たす \( b_i \) の組み合わせは、\( k = S – 3n \) として、
\[ {}_{k + n – 1} \mathrm{ C }_{n – 1}\]
個あります。したがって、\( 1 \leq n \leq \left \lfloor \dfrac{S}{3} \right \rfloor+ 1 \) の範囲で全探索します。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; // a^n mod を計算する ll modpow(ll a, ll n, ll mod) { ll res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } // a^{-1} mod を計算する ll modinv(ll a, ll mod) { return modpow(a, mod - 2, mod); } const int MAX = 510000; const ll MOD = 1000000007; ll fac[MAX], finv[MAX], inv[MAX]; // テーブルを作る前処理 void COMinit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX; i++){ fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } } // 二項係数計算 ll COM(int n, int k){ if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD; } int main() { int S; cin >> S; ll ans = 0; COMinit(); for (int i = 1; i < S / 3 + 1; i++) { int k = S - 3 * i; ans += COM(k + i - 1, i - 1); ans %= MOD; } cout << ans << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません