結果
| 問題 | No.117 組み合わせの数 |
| ユーザー |
 bayashi-cl
|
| 提出日時 | 2022-03-02 02:18:55 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 11,399 bytes |
| コンパイル時間 | 1,342 ms |
| コンパイル使用メモリ | 132,168 KB |
| 実行使用メモリ | 27,972 KB |
| 最終ジャッジ日時 | 2024-07-08 09:50:12 |
| 合計ジャッジ時間 | 2,945 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
ソースコード
#line 1 "test/math/combination.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/117"
#line 2 "core/stdlib.hpp"
#ifndef LOCAL
#define NDEBUG
#endif
#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <vector>
namespace bys {
using std::array, std::vector, std::string, std::set, std::map, std::pair;
using std::cin, std::cout, std::endl;
using std::min, std::max, std::sort, std::reverse, std::abs, std::pow;
// alias
using ll = long long int;
using ld = long double;
using Pa = pair<int, int>;
using Pall = pair<ll, ll>;
using ibool = std::int8_t;
template <class T>
using uset = std::unordered_set<T>;
template <class S, class T>
using umap = std::unordered_map<S, T>;
} // namespace bys
#line 3 "core/const.hpp"
namespace bys {
constexpr int MOD = 998244353;
constexpr int MOD7 = 1000000007;
constexpr int INF = std::numeric_limits<int>::max() / 2;
constexpr ll LINF = std::numeric_limits<ll>::max() / 2;
} // namespace bys
#line 4 "math/combination.hpp"
namespace bys {
struct MultiComb {
int _n;
int mod;
vector<ll> fact, factinv, inv;
MultiComb(int n, int mod = MOD) : _n(n), mod(mod) {
fact.resize(_n + 1);
factinv.resize(_n + 1);
inv.resize(_n + 1);
fact[0] = fact[1] = 1;
factinv[0] = factinv[1] = 1;
inv[1] = 1;
for (int i = 2; i <= _n; i++) {
fact[i] = fact[i - 1] * i % mod;
inv[i] = mod - inv[mod % i] * (mod / i) % mod;
factinv[i] = factinv[i - 1] * inv[i] % mod;
}
}
ll comb(int n, int r) {
if (r < 0 || n < r) return 0;
return fact[n] * (factinv[r] * factinv[n - r] % mod) % mod;
}
ll perm(int n, int r) {
if (r < 0 || n < r) return 0;
return fact[n] * factinv[n - r] % mod;
}
ll hom(int n, int r) { return comb(n + r - 1, r); }
};
template <class T>
T comb(T n, int r) {
T num = 1, den = 1;
for (int i = 0; i < r; ++i) {
num *= n - i;
den *= i + 1;
}
return num / den;
}
} // namespace bys
#line 3 "test/math/combination.test.cpp"
#line 4 "core/types.hpp"
#include <utility>
namespace bys {
template <class, class = void>
struct has_lshift_to_ostream : std::false_type {};
template <class T>
struct has_lshift_to_ostream<T, std::void_t<decltype(std::declval<std::ostream&>() << std::declval<T&>())>> : std::true_type {};
template <class, class = void>
struct has_rshift_from_istream : std::false_type {};
template <class T>
struct has_rshift_from_istream<T, std::void_t<decltype(std::declval<std::istream&>() >> std::declval<T&>())>> : std::true_type {};
template <class T, class = void>
struct has_tuple_interface : std::false_type {};
template <class T>
struct has_tuple_interface<T, std::void_t<decltype(std::tuple_size<T>())>> : std::true_type {};
template <class, class = void>
struct has_iterator : std::false_type {};
template <class T>
struct has_iterator<T, std::void_t<typename T::iterator>> : std::true_type {};
struct Int1 {};
} // namespace bys
#line 4 "core/printer.hpp"
namespace bys {
struct Printer {
Printer(std::ostream& os_) : os(os_) {}
~Printer() { os << std::flush; }
template <class T>
void cat(T&& v) {
if constexpr (has_lshift_to_ostream<std::decay_t<T>>::value) {
os << v;
} else if constexpr (has_iterator<std::decay_t<T>>::value) {
string sep2;
if constexpr (has_iterator<std::decay_t<typename std::decay_t<T>::value_type>>::value) {
sep2 = _end;
} else {
sep2 = _sep;
}
for (auto &&itr = std::begin(v), end = std::end(v); itr != end; ++itr) {
cat(*itr);
if (std::next(itr) != end) cat(sep2);
}
} else if constexpr (has_tuple_interface<std::decay_t<T>>::value) {
print_tuple(std::forward<T>(v), std::make_index_sequence<std::tuple_size_v<std::decay_t<T>>>());
} else {
static_assert([] { return false; }(), "type error");
}
}
void print() { cat(_end); }
template <class T>
void print(T&& top) {
cat(std::forward<T>(top));
cat(_end);
}
template <class T, class... Ts>
void print(T&& top, Ts&&... args) {
cat(std::forward<T>(top));
cat(_sep);
print(std::forward<Ts>(args)...);
}
template <class... Ts>
void operator()(Ts&&... args) {
print(std::forward<Ts>(args)...);
}
void flush() { os << std::flush; }
template <class... Ts>
void send(Ts&&... args) {
print(std::forward<Ts>(args)...);
flush();
}
Printer set(string sep_ = " ", string end_ = "\n") {
_sep = sep_;
_end = end_;
return *this;
}
void lf() { cat(_end); }
private:
std::ostream& os;
std::string _sep = " ", _end = "\n";
template <std::size_t I, class T>
inline void print_tuple_element(T&& elem) {
if constexpr (I != 0) cat(_sep);
cat(std::forward<T>(elem));
}
template <class Tp, std::size_t... I>
inline void print_tuple(Tp&& tp, std::index_sequence<I...>) {
(print_tuple_element<I>(std::forward<decltype(std::get<I>(tp))>(std::get<I>(tp))), ...);
}
};
} // namespace bys
#line 4 "core/scanner.hpp"
namespace bys {
struct Scanner {
Scanner(std::istream& is_) : is(is_){};
template <class... Ts>
void scan(Ts&... args) {
(is >> ... >> args);
}
template <class T, class... Us>
decltype(auto) read() {
if constexpr (sizeof...(Us) == 0) {
if constexpr (has_rshift_from_istream<T>::value) {
T res;
is >> res;
return res;
} else if constexpr (has_tuple_interface<T>::value) {
auto res = read_tuple<T>(std::make_index_sequence<std::tuple_size_v<T>>());
return res;
} else if constexpr (std::is_same_v<T, Int1>) {
int res;
is >> res;
--res;
return res;
} else if constexpr (has_iterator<T>::value) {
//! TODO: 一行読んでsplit
static_assert([] { return false; }(), "NotImplementedError");
} else {
static_assert([] { return false; }(), "TypeError");
}
} else {
return std::tuple{read<T>(), read<Us>()...};
}
}
template <class T, std::size_t N, typename R = std::conditional_t<std::is_same_v<T, Int1>, int, T>>
std::array<R, N> read() {
std::array<R, N> res;
for (auto&& e : res) e = read<T>();
return res;
}
template <class T, typename R = std::conditional_t<std::is_same_v<T, Int1>, int, T>>
vector<R> readvec(int n) {
vector<R> res(n);
for (auto&& e : res) e = read<T>();
return res;
}
template <class T, typename R = std::conditional_t<std::is_same_v<T, Int1>, int, T>>
vector<vector<R>> readvec(int n, int m) {
vector<vector<R>> res(n);
for (auto&& e : res) e = readvec<T>(m);
return res;
}
template <class Lambda = std::function<int(std::string)>,
typename T = std::invoke_result_t<std::decay_t<Lambda>, std::string>>
std::vector<T> readln(
Lambda f = [](string x) { return std::stoi(x); }, char sep = ' ') {
std::ws(is);
std::string elem;
std::getline(is, elem);
std::stringstream ss{elem};
std::vector<T> res;
while (std::getline(ss, elem, sep)) res.emplace_back(f(elem));
return res;
}
std::string getline(bool skip_ws = true) {
if (skip_ws) std::ws(is);
std::string res;
std::getline(is, res);
return res;
}
private:
std::istream& is;
template <class Tp, std::size_t... I>
inline decltype(auto) read_tuple(std::index_sequence<I...>) {
return Tp{read<typename std::tuple_element_t<I, Tp>>()...};
}
};
} // namespace bys
#line 5 "core/io.hpp"
namespace bys {
__attribute__((constructor)) void setup_io() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << std::fixed << std::setprecision(11);
std::cerr << std::fixed << std::setprecision(11);
std::cerr << std::boolalpha;
}
Printer print(std::cout), debug(std::cerr);
Scanner scanner(std::cin);
} // namespace bys
#line 2 "core/macro.hpp"
// clang-format off
/**
* @brief マクロ
*/
#ifdef LOCAL
//! @brief デバッグ用出力 ジャッジ上では何もしない。
#define DEBUG(...) { std::cerr << "[debug] line" << std::setw(4) << __LINE__ << ": "; debug(__VA_ARGS__); }
#else
#define DEBUG(...)
#endif
//! @brief printしてreturnする。
#define EXIT(...) { print(__VA_ARGS__); return; }
#define CONCAT_IMPL(a, b) a##b
#define CONCAT(a, b) CONCAT_IMPL(a, b)
//! @brief [[maybe_unused]]な変数を生成。
#define UV [[maybe_unused]] auto CONCAT(unused_val_, __LINE__)
#define RE std::runtime_error("line: " + std::to_string(__LINE__) + ", func: " + __func__)
// clang-format on
#line 2 "core/solver.hpp"
namespace bys {
struct Solver {
int IT = 1;
Solver() {}
void solve();
void solve(int rep) {
for (; IT <= rep; ++IT) solve();
}
};
} // namespace bys
#line 2 "utility/range.hpp"
namespace bys {
//! @brief Pythonのrange
template <typename T>
struct Range {
Range(T start, T stop, T step = 1) : it(start), stop(stop), step(step), dir(step >= 0 ? 1 : -1) {}
Range(T stop) : it(0), stop(stop), step(1), dir(1) {}
Range<T> begin() const { return *this; }
T end() const { return stop; }
bool operator!=(const T val) const { return (val - it) * dir > 0; }
void operator++() { it += step; }
const T& operator*() const { return it; }
private:
T it;
const T stop, step;
const int dir;
friend Range reversed(const Range& r) {
auto new_start = (r.stop - r.dir - r.it) / r.step * r.step + r.it;
return {new_start, r.it - r.dir, -r.step};
}
};
template <class T>
Range<T> irange(T stop) {
return Range(stop);
}
template <class T>
Range<T> irange(T start, T stop, T step = 1) {
return Range(start, stop, step);
}
} // namespace bys
#line 6 "test/math/combination.test.cpp"
namespace bys {
std::tuple<char, int, int> parse(string s) {
s.pop_back();
std::replace(s.begin(), s.end(), ',', ' ');
std::stringstream ss{s.substr(2)};
int n, r;
ss >> n >> r;
return {s[0], n, r};
}
void Solver::solve() {
auto t = scanner.read<int>();
int MAX = 1'000'000;
MultiComb mc(MAX, MOD7);
for (UV : irange(t)) {
auto [t, n, r] = parse(scanner.read<string>());
if (t == 'C') {
print(mc.comb(n, r));
} else if (t == 'P') {
print(mc.perm(n, r));
} else if (t == 'H') {
print(mc.hom(n, r));
} else {
throw RE;
}
}
}
} // namespace bys
int main() {
bys::Solver solver;
solver.solve(/* bys::scanner.read<int>() */);
return 0;
}