結果
| 問題 |
No.790 ちきんの括弧並べ
|
| ユーザー |
 Pachicobue
|
| 提出日時 | 2019-02-20 22:03:49 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 6,403 bytes |
| コンパイル時間 | 1,770 ms |
| コンパイル使用メモリ | 196,380 KB |
| 最終ジャッジ日時 | 2025-01-06 21:17:55 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 10 |
ソースコード
#include <bits/stdc++.h>
//!===========================================================!//
//! dP dP dP !//
//! 88 88 88 !//
//! 88aaaaa88a .d8888b. .d8888b. .d888b88 .d8888b. 88d888b. !//
//! 88 88 88ooood8 88' `88 88' `88 88ooood8 88' `88 !//
//! 88 88 88. ... 88. .88 88. .88 88. ... 88 !//
//! dP dP `88888P' `88888P8 `88888P8 `88888P' dP !//
//!===========================================================!//
using ld = long double;
using ll = long long;
std::mt19937 mt{std::random_device{}()};
template <typename F>
constexpr F PI() { return 3.1415926535897932385; }
template <typename T, std::size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& v)
{
os << "[";
for (const auto& e : v) { os << e << ","; }
return (os << "]" << std::endl);
}
template <typename T, typename A>
std::ostream& operator<<(std::ostream& os, const std::deque<T, A>& v)
{
os << "[";
for (const auto& e : v) { os << e << ","; }
return (os << "]" << std::endl);
}
template <typename K, typename T, typename C, typename A>
std::ostream& operator<<(std::ostream& os, const std::multimap<K, T, C, A>& v)
{
os << "[";
for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; }
return (os << "]" << std::endl);
}
template <typename T, typename C, typename A>
std::ostream& operator<<(std::ostream& os, const std::multiset<T, C, A>& v)
{
os << "[";
for (const auto& e : v) { os << e << ","; }
return (os << "]" << std::endl);
}
template <typename K, typename T, typename C, typename A>
std::ostream& operator<<(std::ostream& os, const std::map<K, T, C, A>& v)
{
os << "[";
for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; }
return (os << "]" << std::endl);
}
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& v) { return (os << "<" << v.first << "," << v.second << ">"); }
template <typename T1, typename T2, typename T3>
std::ostream& operator<<(std::ostream& os, const std::priority_queue<T1, T2, T3>& v)
{
auto q = v;
os << "[";
while (not q.empty()) { os << q.top() << ",", q.pop(); }
return os << "]\n";
}
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::queue<T1>& v)
{
auto q = v;
os << "[";
while (not q.empty()) { os << q.front() << ",", q.pop(); }
return os << "]\n";
}
template <typename T, typename C, typename A>
std::ostream& operator<<(std::ostream& os, const std::set<T, C, A>& v)
{
os << "[";
for (const auto& e : v) { os << e << ","; }
return (os << "]" << std::endl);
}
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::stack<T1>& v)
{
auto q = v;
os << "[";
while (not q.empty()) { os << q.top() << ",", q.pop(); }
return os << "]\n";
}
template <typename K, typename T, typename H, typename P, typename A>
std::ostream& operator<<(std::ostream& os, const std::unordered_multimap<K, T, H, P, A>& v)
{
os << "[";
for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; }
return (os << "]" << std::endl);
}
template <typename T, typename H, typename P, typename A>
std::ostream& operator<<(std::ostream& os, const std::unordered_multiset<T, H, P, A>& v)
{
os << "[";
for (const auto& e : v) { os << e << ","; }
return (os << "]" << std::endl);
}
template <typename K, typename T, typename H, typename P, typename A>
std::ostream& operator<<(std::ostream& os, const std::unordered_map<K, T, H, P, A>& v)
{
os << "[";
for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; }
return (os << "]" << std::endl);
}
template <typename T, typename H, typename P, typename A>
std::ostream& operator<<(std::ostream& os, const std::unordered_set<T, H, P, A>& v)
{
os << "[";
for (const auto& e : v) { os << e << ","; }
return (os << "]" << std::endl);
}
template <typename T, typename A>
std::ostream& operator<<(std::ostream& os, const std::vector<T, A>& v)
{
os << "[";
for (const auto& e : v) { os << e << ","; }
return (os << "]" << std::endl);
}
#define show(x) std::cerr << #x << " = " << (x) << std::endl
//!===============================================================================!//
//! 8888ba.88ba dP a88888b. dP oo !//
//! 88 `8b `8b 88 d8' `88 88 !//
//! 88 88 88 .d8888b. .d888b88 88 .d8888b. 88d8b.d8b. 88d888b. dP !//
//! 88 88 88 88' `88 88' `88 88 88' `88 88'`88'`88 88' `88 88 !//
//! 88 88 88 88. .88 88. .88 Y8. .88 88. .88 88 88 88 88. .88 88 !//
//! dP dP dP `88888P' `88888P8 Y88888P' `88888P' dP dP dP 88Y8888' dP !//
//!===============================================================================!//
template <ll mod>
class ModComb
{
public:
ModComb(const std::size_t n) : in(n + 1, 1), f(n + 1, 1), invf(n + 1, 1)
{
for (ll i = 2; i <= (ll)n; i++) { f[i] = (f[i - 1] * i) % mod, in[i] = ((mod - (mod / i)) * in[mod % i]) % mod, invf[i] = (invf[i - 1] * in[i]) % mod; }
}
ll fact(const std::size_t n) const { return f[n]; }
ll inv(const std::size_t n) const { return in[n]; }
ll invFact(const std::size_t n) const { return invf[n]; }
ll perm(const std::size_t n, const std::size_t k) const { return f[n] * invf[n - k] % mod; }
ll comb(const std::size_t n, const std::size_t k) const { return (f[n] * invf[k] % mod) * invf[n - k] % mod; }
private:
std::vector<ll> in, f, invf;
};
//!============================================!//
//! 8888ba.88ba oo !//
//! 88 `8b `8b !//
//! 88 88 88 .d8888b. dP 88d888b. !//
//! 88 88 88 88' `88 88 88' `88 !//
//! 88 88 88 88. .88 88 88 88 !//
//! dP dP dP `88888P8 dP dP dP !//
//!============================================!//
int main()
{
int N;
std::cin >> N;
constexpr ll MOD = 1000000007LL;
ModComb<MOD> mod(2 * N);
std::cout << (mod.fact(2 * N) * mod.invFact(N) % MOD) * mod.invFact(N + 1) % MOD << std::endl;
return 0;
}