結果
問題 | No.117 組み合わせの数 |
ユーザー |
|
提出日時 | 2022-03-02 02:55:01 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 11,563 bytes |
コンパイル時間 | 5,237 ms |
コンパイル使用メモリ | 162,568 KB |
最終ジャッジ日時 | 2025-01-28 04:15:35 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | WA * 1 |
ソースコード
#line 1 "test.cpp"#define PROBLEM "https://yukicoder.me/problems/no/117"#line 2 "/home/bayashi/dev/byslib/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;// aliasusing 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 "/home/bayashi/dev/byslib/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 "/home/bayashi/dev/byslib/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 4 "/home/bayashi/dev/byslib/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 "/home/bayashi/dev/byslib/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 "/home/bayashi/dev/byslib/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: 一行読んでsplitstatic_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 "/home/bayashi/dev/byslib/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 "/home/bayashi/dev/byslib/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 "/home/bayashi/dev/byslib/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 "/home/bayashi/dev/byslib/utility/range.hpp"namespace bys {//! @brief Pythonのrangetemplate <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 5 "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 = 2'000'000;MultiComb mc(MAX, MOD7);for (UV : irange(t)) {auto [c, n, r] = parse(scanner.read<string>());if (c == 'C') {print(mc.comb(n, r));} else if (c == 'P') {print(mc.perm(n, r));} else if (c == 'H') {print(mc.hom(n, r));} else {throw RE;}}}} // namespace bysint main() {bys::Solver solver;solver.solve(/* bys::scanner.read<int>() */);return 0;}