結果
問題 | No.2406 Difference of Coordinate Squared |
ユーザー | Focus_Sash |
提出日時 | 2023-08-05 10:52:39 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 4,696 bytes |
コンパイル時間 | 2,446 ms |
コンパイル使用メモリ | 209,084 KB |
実行使用メモリ | 15,224 KB |
最終ジャッジ日時 | 2024-10-15 08:02:24 |
合計ジャッジ時間 | 12,553 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 27 ms
14,932 KB |
testcase_02 | RE | - |
testcase_03 | RE | - |
testcase_04 | RE | - |
testcase_05 | AC | 3 ms
6,816 KB |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | RE | - |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | AC | 23 ms
13,200 KB |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | RE | - |
testcase_20 | RE | - |
testcase_21 | RE | - |
testcase_22 | RE | - |
testcase_23 | RE | - |
testcase_24 | RE | - |
testcase_25 | RE | - |
testcase_26 | RE | - |
testcase_27 | RE | - |
testcase_28 | AC | 2 ms
6,816 KB |
testcase_29 | RE | - |
testcase_30 | AC | 2 ms
6,820 KB |
testcase_31 | RE | - |
testcase_32 | RE | - |
testcase_33 | WA | - |
testcase_34 | RE | - |
testcase_35 | RE | - |
testcase_36 | RE | - |
testcase_37 | RE | - |
testcase_38 | AC | 2 ms
6,816 KB |
testcase_39 | RE | - |
testcase_40 | RE | - |
testcase_41 | AC | 3 ms
6,816 KB |
testcase_42 | RE | - |
testcase_43 | RE | - |
testcase_44 | RE | - |
testcase_45 | RE | - |
testcase_46 | AC | 2 ms
6,820 KB |
testcase_47 | RE | - |
testcase_48 | RE | - |
testcase_49 | RE | - |
testcase_50 | RE | - |
testcase_51 | RE | - |
testcase_52 | RE | - |
testcase_53 | RE | - |
testcase_54 | RE | - |
testcase_55 | RE | - |
testcase_56 | AC | 2 ms
6,816 KB |
ソースコード
#line 1 "b.cpp" #include "bits/stdc++.h" using namespace std; namespace util { using ll = long long; using vl = std::vector<long long>; using pl = std::pair<long long, long long>; } // namespace util using namespace util; #include <atcoder/modint> #line 1 "cp-library/binomial.hpp" #include <cassert> #include <vector> template <typename T> class Binomial { private: int size_, mod_; std::vector<T> fact_, fact_inv_, inv_; public: explicit Binomial(int size) : size_(size), mod_(T::mod()) { fact_.resize(size + 1); fact_inv_.resize(size + 1); inv_.resize(size + 1); fact_[0] = fact_[1] = 1; fact_inv_[0] = fact_inv_[1] = 1; inv_[1] = 1; for (int i = 2; i <= size; ++i) { fact_[i] = fact_[i - 1] * i; inv_[i] = T(mod_) - inv_[mod_ % i] * (mod_ / i); fact_inv_[i] = fact_inv_[i - 1] * inv_[i]; } } T Calc(int n, int k) { assert(n <= size_ && k <= size_); if (k < 0 || n < 0 || n < k) return 0; if (k == 0) { return 1; } return fact_[n] * fact_inv_[n - k] * fact_inv_[k]; } T Factorial(int k) { assert(k >= 0 && k <= size_); return fact_[k]; } T FactorialInv(int k) { assert(k >= 0 && k <= size_); return fact_inv_[k]; } }; #line 2 "cp-library/cutils.hpp" #include <cmath> constexpr long long kMax = std::numeric_limits<long long>::max(); inline long long CountDigit(long long n, const long long base = 10) { assert(n > 0); assert(base > 1); long long res = 0; while (n) { res++; n /= base; } return res; } // verified inline long long Pow(long long x, long long n) { assert(n >= 0); if (x == 0) return 0; long long res = 1LL; while (n > 0) { if (n & 1) { assert(x != 0 && std::abs(res) <= kMax / std::abs(x)); res = res * x; } if (n >>= 1) { assert(x != 0 && std::abs(x) <= kMax / std::abs(x)); x = x * x; } } return res; } // verified inline long long Mod(long long n, const long long m) { // returns the "arithmetic modulo" // for a pair of integers (n, m) with m != 0, there exists a unique pair of // integer (q, r) s.t. n = qm + r and 0 <= r < |m| returns this r assert(m != 0); if (m < 0) return Mod(n, -m); if (n >= 0) return n % m; else return (m + n % m) % m; } inline long long Quotient(long long n, long long m) { // returns the "arithmetic quotient" assert((n - Mod(n, m)) % m == 0); return (n - Mod(n, m)) / m; } inline long long DivFloor(long long n, long long m) { // returns floor(n / m) assert(m != 0); if (m < 0) { n = -n; m = -m; } if (n >= 0) return n / m; else if (n % m == 0) return -(std::abs(n) / m); else return -(std::abs(n) / m) - 1; } inline long long DivCeil(long long n, long long m) { // returns ceil(n / m) assert(m != 0); if (n % m == 0) return DivFloor(n, m); else return DivFloor(n, m) + 1; } inline long long PowMod(long long x, long long n, const long long m) { assert(n >= 0); assert(m != 0); if (x == 0) return 0; long long res = 1; x = Mod(x, m); while (n > 0) { if (n & 1) { assert(x == 0 || std::abs(res) <= kMax / std::abs(x)); res = Mod(res * x, m); } if (n >>= 1) { assert(x == 0 || std::abs(x) <= kMax / std::abs(x)); x = Mod(x * x, m); } } return res; } long long SqrtFloor(long long n) { // n -> floor(sqrt(n)) assert(n >= 0); if (n == 0) return 0; long long ok = 0; long long ng = n + 1; while (ng - ok > 1) { long long mid = (ok + ng) / 2; if (mid <= n / mid) { ok = mid; } else { ng = mid; } } return ok; } long long SqrtCeil(long long n) { // n -> ceil(sqrt(n)) assert(n >= 0); if (n == 0) return 0; long long ok = n; long long ng = 0; while (ok - ng > 1) { long long mid = (ok + ng) / 2; if (mid >= n / mid) { ok = mid; } else { ng = mid; } } return ok; } #line 14 "b.cpp" using namespace atcoder; using mint = modint998244353; void solve() { ll n, m; cin >> n >> m; mint ans = 0; Binomial<mint> binom(n + 1); for (ll y = -n; y <= n; ++y) { if (m + y * y < 0) continue; if (SqrtCeil(m + y * y) != SqrtFloor(m + y * y)) continue; ll x = SqrtCeil(m + y * y); if ((x + y + n) % 2) continue; ans += binom.Calc(n, (x + y + n) / 2) * binom.Calc(n, (x - y + n) / 2); if (x != 0) { ans += binom.Calc(n, (-x + y + n) / 2) * binom.Calc(n, (-x - y + n) / 2); } } ans *= mint(4).inv().pow(n); cout << ans.val() << '\n'; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(15); solve(); return 0; }