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

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

Test cases

Env	Name	Status	Elapsed	Memory
g++	hand_01	AC	50 ms	32 MB
g++	hand_02	AC	49 ms	33 MB
g++	hand_03	AC	48 ms	33 MB
g++	hand_04	AC	47 ms	33 MB
g++	random_01	AC	47 ms	33 MB
g++	random_02	AC	48 ms	32 MB
g++	random_03	AC	48 ms	32 MB
g++	random_04	AC	49 ms	32 MB
g++	random_05	AC	48 ms	33 MB
g++	random_06	AC	49 ms	32 MB
g++	random_07	AC	48 ms	32 MB
g++	random_08	AC	47 ms	32 MB
g++	random_09	AC	48 ms	33 MB
g++	random_10	AC	48 ms	32 MB
g++	random_11	AC	47 ms	33 MB
g++	random_12	AC	48 ms	32 MB
g++	random_13	AC	47 ms	33 MB
g++	random_14	AC	47 ms	32 MB
g++	random_15	AC	47 ms	33 MB
g++	random_16	AC	48 ms	32 MB
g++	random_17	AC	48 ms	33 MB
g++	random_18	AC	47 ms	33 MB
g++	random_19	AC	47 ms	32 MB
g++	random_20	AC	47 ms	33 MB
g++	random_21	AC	47 ms	33 MB
g++	random_22	AC	47 ms	32 MB
g++	random_23	AC	47 ms	32 MB
g++	random_24	AC	48 ms	33 MB
g++	sample_01	AC	47 ms	33 MB
g++	sample_02	AC	48 ms	32 MB
g++	sample_03	AC	48 ms	33 MB
clang++	hand_01	AC	34 ms	40 MB
clang++	hand_02	AC	35 ms	40 MB
clang++	hand_03	AC	35 ms	42 MB
clang++	hand_04	AC	34 ms	44 MB
clang++	random_01	AC	34 ms	44 MB
clang++	random_02	AC	35 ms	40 MB
clang++	random_03	AC	35 ms	38 MB
clang++	random_04	AC	33 ms	36 MB
clang++	random_05	AC	34 ms	40 MB
clang++	random_06	AC	34 ms	40 MB
clang++	random_07	AC	36 ms	42 MB
clang++	random_08	AC	34 ms	38 MB
clang++	random_09	AC	34 ms	38 MB
clang++	random_10	AC	34 ms	40 MB
clang++	random_11	AC	35 ms	36 MB
clang++	random_12	AC	34 ms	40 MB
clang++	random_13	AC	34 ms	40 MB
clang++	random_14	AC	35 ms	42 MB
clang++	random_15	AC	33 ms	38 MB
clang++	random_16	AC	34 ms	42 MB
clang++	random_17	AC	33 ms	38 MB
clang++	random_18	AC	34 ms	36 MB
clang++	random_19	AC	35 ms	38 MB
clang++	random_20	AC	35 ms	42 MB
clang++	random_21	AC	34 ms	44 MB
clang++	random_22	AC	34 ms	44 MB
clang++	random_23	AC	34 ms	40 MB
clang++	random_24	AC	36 ms	44 MB
clang++	sample_01	AC	35 ms	42 MB
clang++	sample_02	AC	35 ms	38 MB
clang++	sample_03	AC	35 ms	40 MB

Back to top page