結果
| 問題 | No.2383 Naphthol |
| ユーザー |
 Shell-Wataru
|
| 提出日時 | 2023-07-14 23:14:01 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 10 ms / 2,000 ms |
| コード長 | 4,569 bytes |
| コンパイル時間 | 2,633 ms |
| コンパイル使用メモリ | 148,524 KB |
| 最終ジャッジ日時 | 2025-02-15 14:43:17 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 18 |
ソースコード
#include <iostream>#include <algorithm>#include <vector>#include <deque>#include <queue>#include <set>#include <map>#include <limits>#include <cmath>#include <iomanip>#include <functional>#include <random>#include <set>#include <atcoder/string>#include <atcoder/math>#include <unordered_map>#include <climits>using namespace std;using ll = long long;using namespace atcoder;const long long BASE_NUM = 998244353;// https://scrapbox.io/pocala-kyopro/%E6%8B%A1%E5%BC%B5%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95// https://ei1333.github.io/luzhiled/snippets/math/combination.htmltemplate <int mod>struct ModInt{int x;ModInt() : x(0) {}ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}ModInt &operator+=(const ModInt &p){if ((x += p.x) >= mod)x -= mod;return *this;}ModInt &operator-=(const ModInt &p){if ((x += mod - p.x) >= mod)x -= mod;return *this;}ModInt &operator*=(const ModInt &p){x = (int)(1LL * x * p.x % mod);return *this;}ModInt &operator/=(const ModInt &p){*this *= p.inverse();return *this;}ModInt operator-() const { return ModInt(-x); }ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }bool operator==(const ModInt &p) const { return x == p.x; }bool operator!=(const ModInt &p) const { return x != p.x; }ModInt inverse() const{int a = x, b = mod, u = 1, v = 0, t;while (b > 0){t = a / b;swap(a -= t * b, b);swap(u -= t * v, v);}return ModInt(u);}ModInt pow(int64_t n) const{ModInt ret(1), mul(x);while (n > 0){if (n & 1)ret *= mul;mul *= mul;n >>= 1;}return ret;}friend ostream &operator<<(ostream &os, const ModInt &p){return os << p.x;}friend istream &operator>>(istream &is, ModInt &a){int64_t t;is >> t;a = ModInt<mod>(t);return (is);}static int get_mod() { return mod; }};using modint = ModInt<BASE_NUM>;template <typename T>struct Combination{vector<T> _fact, _rfact, _inv;Combination(int sz) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1){_fact[0] = _rfact[sz] = _inv[0] = 1;for (int i = 1; i <= sz; i++)_fact[i] = _fact[i - 1] * i;_rfact[sz] /= _fact[sz];for (int i = sz - 1; i >= 0; i--)_rfact[i] = _rfact[i + 1] * (i + 1);for (int i = 1; i <= sz; i++)_inv[i] = _rfact[i] * _fact[i - 1];}inline T fact(int k) const { return _fact[k]; }inline T rfact(int k) const { return _rfact[k]; }inline T inv(int k) const { return _inv[k]; }T P(int n, int r) const{if (r < 0 || n < r)return 0;return fact(n) * rfact(n - r);}T C(int p, int q) const{if (q < 0 || p < q)return 0;return fact(p) * rfact(q) * rfact(p - q);}T H(int n, int r) const{if (n < 0 || r < 0)return (0);return r == 0 ? 1 : C(n + r - 1, r);}};using modint = ModInt<BASE_NUM>;int solve(){ll N,K;cin >> N >> K;Combination<modint> C(300000);if (N == 1){modint ans = 0;for(int i = 0;i < 6;i++){if (i == 0){ans += C.C(6,K);}else{ll e = gcd(i,6);ll d = 6/e;if (K % d == 0){ans += C.C(e,K/d);}}}for(int i = 0;i <= 2;i++){if ( (K-i) % 2 == 0 && K-i >= 0){ans += C.C(2,i) * C.C(2,(K-i)/2) *3;}}if ( K % 2 == 0){ans += C.C(3,K/2) *3;}ans /= 12;cout << ans << endl;}else{modint ans = 0;ans += C.C(2*N+4,K);//恒等if (K % 2 == 0){ans += C.C(N+2,K/2);//180度回転}if (K % 2 == 0){ans += C.C(N+2,K/2);//線対称横}if (N % 2 == 0){if (K % 2 == 0){ans += C.C(N+2,K/2);//線対称横}}else{for(int i = 0;i <= 2;i++){if ( (K-i) % 2 == 0 && K-i >= 0){ans += C.C(2,i) * C.C(N+1,(K-i)/2);//線対称縦}}}ans /= 4;cout << ans << endl;}return 0;}int main(){// ll T;// cin >> T;// while(T--){solve();// }return 0;}