Submission #6421249

---

Source Code Expand

#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << '\n';
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = (int)1e9;
int MOD = INF + 7;

#ifndef FACT
#define FACT
// return n! mod p
int fact(int n, int p = __INT32_MAX__){
	static vector<int> memo_in_fact(1, 1);
	if ((int) memo_in_fact.size() <= n) {
		int l = memo_in_fact.size();
		memo_in_fact.resize(n+1);
		for(int i = l; i <= n; i++) memo_in_fact[i] = ((ll) memo_in_fact[i-1] * i) % p;
	}
	return memo_in_fact[n];
}
#endif

#ifndef MOD_FACT
#define MOD_FACT
// return a mod p (when n!=a*p^e), o(log_p n)
int modFact(int n, int& e, int p = __INT32_MAX__){
	e = 0;
	if(n == 0) return 1;

	int res = modFact(n / p, e, p);
	e += n / p;

	if((n / p % 2 != 0)) return (long long) res * (p - fact(n % p, p)) % p;
	return (long long) res * fact(n % p, p) % p;
}
#endif

#ifndef GCD
#define GCD
// solve ax+by=gcd(a, b)
// return gcd(a, b)
template<class T>
T gcd(const T a, const T b, T* const px = nullptr, T* const py = nullptr){
	if(py == nullptr){
		if(b == 0) return a;
		return gcd(b, a % b);
	}

	T d = a;
	if(b != 0){
		d = gcd(b, a % b, py, px);
		*py -= (a / b) * *px;
	}else{
		*px = 1; *py = 0;
	}
	return d;
}
#endif

#ifndef MOD_INVERSE
#define MOD_INVERSE
// return a^(-1) (mod m)
template<class T>
 T modInverse(T a, T m){
	 T x, y;
	 assert(gcd(a, m, &x, &y) == 1);
	 return (m + x % m) % m;
 }
#endif

#ifndef COMBINATION
#define COMBINATION
// return nPk mod p
int perm(int n, int k, int p = __INT32_MAX__){
	if(n < 0 or k < 0 or n < k) return 0;
	int e1, e2;
	int a1 = modFact(n, e1, p), a2 = modFact(n - k, e2, p);
	return (long long) a1 * modInverse(a2, p) % p;
}

// return nCk mod p, o(log_p n)
int comb(int n, int k, int p = __INT32_MAX__){
	if(n < 0 or k < 0 or n < k) return 0;
	int e1, e2, e3;
	int a1 = modFact(n, e1, p), a2 = modFact(k, e2, p), a3 = modFact(n - k, e3, p);
	if(e1 > e2 + e3) return 0;
	return (long long) a1 * modInverse((long long) a2 * a3 % p, (long long) p) % p;
}

// return nHk mod p
int hcomb(int n, int k, int p = __INT32_MAX__){
	if(n < 0 or k < 0) return 0;
	if(n == 0 and k == 0) return 1;
	return comb(n + k - 1, k, p);
}
#endif

int n, k;


int main(void){
    cin >> n >> k;
    cout << hcomb(n, k, MOD) << '\n';

    return 0;
}

Submission Info

Judge Result