結果
問題 |
No.3033 エルハートの数え上げ
|
ユーザー |
|
提出日時 | 2025-02-21 23:50:31 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 9,799 bytes |
コンパイル時間 | 3,809 ms |
コンパイル使用メモリ | 288,324 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-02-21 23:50:36 |
合計ジャッジ時間 | 4,998 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#line 2 "template.hpp" // #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; // https://xn--kst.jp/blog/2019/08/29/cpp-comp/ // debug methods // usage: debug(x,y); // vector 出力できるように修正 template <typename T> ostream& debug_print(ostream& os, const vector<T>& v) { os << "["; for (size_t i = 0; i < v.size(); ++i) { os << v[i]; if (i < v.size() - 1) os << ", "; } os << "]"; return os; } template <typename T> ostream& debug_print(ostream& os, const T& var) { os << var; return os; } #define CHOOSE(a) CHOOSE2 a #define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x #define debug_1(x1) { cout << #x1 << ": "; debug_print(cout, x1) << endl; } #define debug_2(x1, x2) { cout << #x1 << ": "; debug_print(cout, x1) << ", " << #x2 << ": "; debug_print(cout, x2) << endl; } #define debug_3(x1, x2, x3) { cout << #x1 << ": "; debug_print(cout, x1) << ", " << #x2 << ": "; debug_print(cout, x2) << ", " << #x3 << ": "; debug_print(cout, x3) << endl; } #define debug_4(x1, x2, x3, x4) { cout << #x1 << ": "; debug_print(cout, x1) << ", " << #x2 << ": "; debug_print(cout, x2) << ", " << #x3 << ": "; debug_print(cout, x3) << ", " << #x4 << ": "; debug_print(cout, x4) << endl; } #define debug_5(x1, x2, x3, x4, x5) { cout << #x1 << ": "; debug_print(cout, x1) << ", " << #x2 << ": "; debug_print(cout, x2) << ", " << #x3 << ": "; debug_print(cout, x3) << ", " << #x4 << ": "; debug_print(cout, x4) << ", " << #x5 << ": "; debug_print(cout, x5) << endl; } #ifdef LOCAL #define debug(...) CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~))(__VA_ARGS__) #else #define debug(...) #endif using ll = long long; using vl = vector<ll>; using Graph = vector<vector<ll>>; using P = pair<ll, ll>; #define all(v) v.begin(), v.end() template <typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); } template <typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); } #define rep1(i, n) for(ll i = 1; i <= ((ll)n); ++i) // https://trap.jp/post/1224/ template <class... T> constexpr auto min(T... a) { return min(initializer_list<common_type_t<T...>>{a...}); } template <class... T> constexpr auto max(T... a) { return max(initializer_list<common_type_t<T...>>{a...}); } template <class... T> void input(T &...a) { (cin >> ... >> a); } template <class T> void input(vector<T> &a) { for(T &x : a) cin >> x; } void print() { cout << '\n'; } template <class T, class... Ts> void print(const T &a, const Ts &...b) { cout << a; (cout << ... << (cout << ' ', b)); cout << '\n'; } void print(const string &s) { cout << s << '\n'; } template <class Container, typename = void> struct is_container : std::false_type {}; template <class Container> struct is_container<Container, std::void_t<decltype(std::declval<Container>().begin()), decltype(std::declval<Container>().end())>> : std::true_type {}; template <class Container> typename enable_if<is_container<Container>::value>::type print(const Container& x) { if (!x.empty()) { auto it = x.begin(); for (; it != prev(x.end()); ++it) { cout << *it << " "; } cout << *it << "\n"; // 最後の要素を出力して改行 } } #define INT(...) \ int __VA_ARGS__; \ input(__VA_ARGS__) #define LL(...) \ long long __VA_ARGS__; \ input(__VA_ARGS__) #define STR(...) \ string __VA_ARGS__; \ input(__VA_ARGS__) #define REP1(a) for(ll i = 0; i < a; i++) #define REP2(i, a) for(ll i = 0; i < a; i++) #define REP3(i, a, b) for(ll i = a; i < b; i++) #define REP4(i, a, b, c) for(ll i = a; i < b; i += c) #define overload4(a, b, c, d, e, ...) e #define rep(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__) ll inf = 3e18; vl dx = {1, -1, 0, 0}; vl dy = {0, 0, 1, -1}; #line 2 "/home/y_midori/cp/04_yukicoder/457/g.cpp" // #include <atcoder/all> // using namespace atcoder; // using mint = modint998244353; // https://ei1333.github.io/luzhiled/snippets/math/lagrange-polynomial.htmlから template <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<998244353>; 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); } }; template <typename T> T lagrange_polynomial(const vector<T> &y, int64_t t) { int N = y.size() - 1; Combination<T> comb(N); if(t <= N) return y[t]; T ret(0); vector<T> dp(N + 1, 1), pd(N + 1, 1); for(int i = 0; i < N; i++) dp[i + 1] = dp[i] * (t - i); for(int i = N; i > 0; i--) pd[i - 1] = pd[i] * (t - i); for(int i = 0; i <= N; i++) { T tmp = y[i] * dp[i] * pd[i] * comb.rfact(i) * comb.rfact(N - i); if((N - i) & 1) ret -= tmp; else ret += tmp; } return ret; } void solve() { LL(n, m); using T = tuple<ll, ll, ll, ll>; vector<T> abcd(m); rep(i, m) { LL(a, b, c, d); abcd[i] = T(a, b, c, d); } vector<modint> f(4, 1); rep(t, 1, 4) { // if(t > 1) // break; ll cnt = 0; ll lim = 16 * t + 5; for(ll i = -lim; i <= lim; i++) for(ll j = -lim; j <= lim; j++) for(ll k = -lim; k <= lim; k++) { bool flag = true; for(auto [a, b, c, d] : abcd) { d *= t; if(a * i + b * j + c * k + d < 0) { flag = false; break; } } if(flag) { // debug(i, j, k); cnt++; } } f[t] = cnt; } // vector<mint> x(4); // rep(i, 4) x[i] = i; // auto g = lagrange_interpolation(x, f); // mint ans = 0; // rep(i, 4) { // ans -= g[i] * (modint(-n).pow(i)); // } ll _n = (998244353 * 2 - n) % 998244353; // _n = (n + 998244353) % 998244353; debug(f, n, _n); modint ans = -lagrange_polynomial(f, _n); // modint ans = lagrange_polynomial(f, n); cout << ans << endl; } int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << std::setprecision(16); int t = 1; rep(_, t) { solve(); } // int N, T; // cin >> N; // vector<modint> A(N + 1); // input(A); // cin >> T; // cout << lagrange_polynomial(A, T) << endl; }