test/math/combination/atcoder_abc145_d.test.cpp

View this file on GitHub
Last update: 2023-09-06 15:21:24+09:00
Problem: https://atcoder.jp/contests/abc145/tasks/abc145_d
Link: View error logs on GitHub Actions

Depends on

組み合わせ (src/math/combination.hpp)

Code

// verification-helper: PROBLEM https://atcoder.jp/contests/abc145/tasks/abc145_d

#include "src/math/combination.hpp"

#include <iostream>

using namespace std;

int main() {
	Combination<long long> comb;
	int x, y;
	cin >> x >> y;
	int xx = -x + 2 * y, yy = 2 * x - y;
	x = xx / 3, y = yy / 3;
	if (xx < 0 || yy < 0 || xx % 3 != 0 || yy % 3 != 0) cout << 0 << endl;
	else cout << comb.combination(x + y, x) << endl;

	return 0;
}

#line 1 "test/math/combination/atcoder_abc145_d.test.cpp"
// verification-helper: PROBLEM https://atcoder.jp/contests/abc145/tasks/abc145_d

#line 1 "src/math/combination.hpp"



#include <array>

template<class T, int SIZE = 1100000, T MOD = 1000000007>
class Combination {
private:
	std::array<T, SIZE> fac, finv, inv;

public:
	Combination() {
		fac[0] = fac[1] = inv[1] = finv[0] = finv[1] = 1;
		for (int i = 2; i < SIZE; ++i) {
			fac[i] = fac[i - 1] * i % MOD;
			inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
			finv[i] = finv[i - 1] * inv[i] % MOD;
		}
	}

	T inverse(int n) { return inv[n]; }

	T factorial(int n) { return fac[n]; }

	T inverse_factorial(int n) { return finv[n]; }

	T permutation(int n, int r) {
		if (n < r || n < 0 || r < 0) return 0;
		return fac(n) * finv(n - r);
	}

	T combination(int n, int r) {
		if (n < r || n < 0 || r < 0) return 0;
		return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
	}
};


#line 4 "test/math/combination/atcoder_abc145_d.test.cpp"

#include <iostream>

using namespace std;

int main() {
	Combination<long long> comb;
	int x, y;
	cin >> x >> y;
	int xx = -x + 2 * y, yy = 2 * x - y;
	x = xx / 3, y = yy / 3;
	if (xx < 0 || yy < 0 || xx % 3 != 0 || yy % 3 != 0) cout << 0 << endl;
	else cout << comb.combination(x + y, x) << endl;

	return 0;
}