💨

ABC 178 | D - Redistribution

2 min read

問題

https://atcoder.jp/contests/abc178/tasks/abc178_d

考えたこと

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;
}

参考

https://qiita.com/drken/items/f2ea4b58b0d21621bd51#2-1-玉区別しない箱区別制限なし

Discussion

ログインするとコメントできます