超初心者が競プロに挑む

初心者からの競プロ練習記録

ABC021D解いてみた

重複組み合わせですね...。高校の頃ひたすら苦手でした。なんとか解説を理解したので、解答を書いてみた。

#include <cstring>
#include <cstdio>
#define MOD (1000*1000*1000+7)

using namespace std;

class FactorialMOD {
public:
  static const int MAX_N = 200000 + 100;
  typedef long long MODINT;
  MODINT facTable[MAX_N+10];
  MODINT invTable[MAX_N+10];

  void generate(int n, MODINT p) {
    memset(facTable, 0, sizeof(facTable));
    memset(invTable, 0, sizeof(invTable));
    facTable[0]=1;
    for(int i=1;i<=n;++i) {
      facTable[i] = (facTable[i-1] * i) % p;
    }

    MODINT power = facTable[n];
    MODINT res = 1;
    MODINT index = p-2;

    for(int i=0;(index>>i) != 0;++i) {
      if( ((index >> i) & 1) == 1) {
        res = (res * power) % p;
      }
      power = (power*power) %p;
    }

    invTable[n] = res;
    for(int i=n;i>=1;--i) {
      invTable[i-1] = (invTable[i] * i) % p;
      if((invTable[i] * facTable[i]) %p != 1) printf("Error");
    }

  }

  MODINT factorial(int n) {
    return facTable[n];
  }

  MODINT inverseFactorial(int n) {
    return invTable[n];
  }
};

FactorialMOD factorialMOD;

long long asMOD(long long  v) {
  return ((v%MOD) + MOD) % MOD;
}

long long combination(int n, int k) {
  if (n<k) return 0;
  return  asMOD(factorialMOD.factorial(n) * factorialMOD.inverseFactorial(k)) *factorialMOD.inverseFactorial(n-k);
}

int main() {
  int n,k;
  scanf("%d%d", &n, &k);
  factorialMOD.generate(FactorialMOD::MAX_N, MOD);
  printf("%lld\n", asMOD(combination(n-1+k, n-1)));
}