💨

ABC 178 | D - Redistribution

2020/11/29に公開

競プロ

重複組み合わせ

tech

問題

考えたこと

$S$ が3より小さいときは答えがないので0である。

数列の長さを変化させてその組み合わせを合計することで答えを求める。すべての項が3以上の整数で総和が $S$ なので数列の最長の長さは $S/3$ である。

数列の長さが1のときは1つしか組み合わせはない。
数列の長さが $k$ のときを考えると以下のように $n$ 個の玉を $k$ 個の区別された箱に0個以上分配するやり方を求める問題である。

これは重複組み合わせなので $_{n + k -1}C_{n}$ で求められる。

コード

実装時のTips

組み合わせはbicoefの構造体を使って求める

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

using mint = modint1000000007;

template <class T>
struct bicoef {
  vector<T> fact_, inv_, finv_;
  constexpr bicoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {
    int MOD = fact_[0].mod();
    for (int i = 2; i < n; i++) {
      fact_[i] = fact_[i - 1] * i;
      inv_[i] = -inv_[MOD % i] * (MOD / i);
      finv_[i] = finv_[i - 1] * inv_[i];
    }
  }
  constexpr T com(int n, int k) const noexcept { // nCk
    if (n < k || n < 0 || k < 0) return 0;
    return fact_[n] * finv_[k] * finv_[n - k];
  }
  constexpr T fact(int n) const noexcept { // n!
    if (n < 0) return 0;
    return fact_[n];
  }
  constexpr T inv(int n) const noexcept {
    if (n < 0) return 0;
    return inv_[n];
  }
  constexpr T finv(int n) const noexcept { // 1/n!
    if (n < 0) return 0;
    return finv_[n];
  }
};

bicoef<mint> bc(5100);  // 二項係数計算

int main() {
  ll s;
  cin >> s;
  if (s < 3) {
    cout << 0 << endl;
    return 0;
  }
  const int md = s / 3;  // 最大の桁
  mint ans = 0;
  for (int k = 1; k <= md; k++) {
    ll n = s - k * 3;
    ans += bc.com(n + k - 1, n);
  }
  cout << ans.val() << endl;
}

ABC 178 | D - Redistribution

問題

考えたこと

コード

参考

Discussion