読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

abc 021

D問題

abc021.contest.atcoder.jp

99点解法

計算量  \displaystyle O(nk)

int n, k;
ll dp[10010][10010];

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  // FROM HERE
  cin >> n >> k;
  RREP(i,0,n) dp[0][i] = 1LL;
  RREP(i,1,k) RREP(j,1,n)
    dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;
  cout << dp[k][n] << endl;
  return 0;
}

100点解法

フェルマーの小定理を用いる

\displaystyle
x^{-1} \equiv x^{p-2}(mod\hspace{2pt}p)\\
p:prime\\

重複組み合わせは

 \displaystyle \begin{equation}
_n \mathrm{H} _k = _{n-1+k} \mathrm{C} _{n-1}\\ \\
_{n-1+k} \mathrm{C} _{n-1} = \frac{(n-1+k)!}{k!(n-1)!}
\end{equation}

という関係が成り立つので後は逆元を求めてあげて解く
逆元は二分累乗法を用いれば \displaystyle O(\log{p})で計算可能
最初に\displaystyle n!をもとめて逐次計算すれば\displaystyle O(n+k+\log{p})に抑えられる

#include <bits/stdc++.h>

#define MOD 1000000007LL
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)

using namespace std;
typedef long long ll;

int n, k;

ll inv(ll x, const ll mod)
{
  ll p = mod - 2;
  ll ans = 1;
  for(; p != 0; p >>= 1LL)
  {
    if(p & 1LL) ans = (ans * x) % mod;
    x = (x * x) % mod;
  }
  return ans;
}

ll c(int a, int b, ll mod)
{
  ll t = 1, f = 1;
  FOR(i,1,b)
  {
    t = t * (a-i+1) % mod;
    f = f * i % mod;
  }
  return t * inv(f,mod) % mod;
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  // FROM HERE
  cin >> n >> k;
  cout << c(n+k-1,k,MOD) << endl;
  return 0;
}