結果
問題 |
No.2383 Naphthol
|
ユーザー |
![]() |
提出日時 | 2023-07-15 14:10:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 27 ms / 2,000 ms |
コード長 | 2,980 bytes |
コンパイル時間 | 704 ms |
コンパイル使用メモリ | 74,116 KB |
最終ジャッジ日時 | 2025-02-15 14:59:46 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#include <iostream> using namespace std; #include <iostream> #include <cassert> template<long long mod> class modint{ private: using T = long long; T a; public: constexpr modint(const long long x = 0) noexcept : a((x%mod+mod)%mod) {} constexpr T& value() noexcept { return a; } constexpr const T& value() const noexcept { return a; } constexpr modint operator-() const noexcept { return modint(0) -= *this; } constexpr modint operator+(const modint& rhs) const noexcept { return modint(*this) += rhs; } constexpr modint operator-(const modint& rhs) const noexcept { return modint(*this) -= rhs; } constexpr modint operator*(const modint& rhs) const noexcept { return modint(*this) *= rhs; } constexpr modint operator/(const modint& rhs) const noexcept { return modint(*this) /= rhs; } constexpr modint& operator+=(const modint& rhs) noexcept { a += rhs.a; if(a >= mod) a -= mod; return *this; } constexpr modint& operator-=(const modint& rhs) noexcept { if(a < rhs.a) a += mod; a -= rhs.a; return *this; } constexpr modint& operator*=(const modint& rhs) noexcept { a = a*rhs.a%mod; return *this; } constexpr modint& operator/=(const modint& rhs) noexcept { return *this *= rhs.inv(); } constexpr bool operator==(const modint& rhs) const noexcept { return a == rhs.a; } constexpr bool operator!=(const modint& rhs) const noexcept { return not (*this == rhs); } constexpr modint pow(long long k) const noexcept { modint ret(1); modint x = k > 0 ? *this : this->inv(); k = abs(k); while(k > 0){ if(k&1) ret *= x; x *= x; k >>= 1; } return ret; } constexpr modint inv() const noexcept { return pow(mod-2); } friend std::ostream& operator<<(std::ostream &os, const modint &X) noexcept { return os << X.a; } friend std::istream& operator>>(std::istream &is, modint &X) noexcept { is >> X.a; X.a %= mod; if(X.a < 0) X.a += mod; return is; } }; #include <vector> #include <cassert> template<typename T> struct Combination { private: int sz; vector<T> F, F_; public: Combination(int sz) : sz(sz), F(sz+1), F_(sz+1) { F[0] = 1; for(int i = 0; i < sz; ++i) F[i+1] = F[i]*(i+1); F_.back() = (T)1/F.back(); for(int i = sz-1; i >= 0; --i) F_[i] = F_[i+1]*(i+1); } T C(int n, int k){ assert(n <= sz); if(n < 0 or k > n) return (T)0; return F[n]*F_[k]*F_[n-k]; } T P(int n, int k){ assert(n <= sz); if(n < 0 or k > n) return (T)0; return F[n]*F_[n-k]; } }; int main(){ using mint = modint<998244353>; int n, k; cin >> n >> k; if(n == 1){ int ans[] = {1,1,3,3,3,1,1}; cout << ans[k] << '\n'; return 0; } Combination<mint> comb(n*2+4); mint ans = comb.C(n*2+4,k); if(k%2 == 0){ ans += comb.C(n+2,k/2)*3; }else if(n%2){ ans += comb.C(n+1,k/2)*2; } cerr << ans << '\n'; cout << ans/4 << '\n'; }