結果
問題 | No.2406 Difference of Coordinate Squared |
ユーザー | Focus_Sash |
提出日時 | 2023-08-05 10:57:50 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 745 ms / 2,000 ms |
コード長 | 4,762 bytes |
コンパイル時間 | 2,357 ms |
コンパイル使用メモリ | 215,136 KB |
実行使用メモリ | 57,488 KB |
最終ジャッジ日時 | 2024-05-05 01:45:42 |
合計ジャッジ時間 | 14,098 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 434 ms
57,472 KB |
testcase_02 | AC | 745 ms
57,484 KB |
testcase_03 | AC | 685 ms
57,488 KB |
testcase_04 | AC | 734 ms
57,488 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 246 ms
28,408 KB |
testcase_07 | AC | 141 ms
24,572 KB |
testcase_08 | AC | 461 ms
37,372 KB |
testcase_09 | AC | 485 ms
38,876 KB |
testcase_10 | AC | 671 ms
54,160 KB |
testcase_11 | AC | 561 ms
47,796 KB |
testcase_12 | AC | 384 ms
51,212 KB |
testcase_13 | AC | 481 ms
49,472 KB |
testcase_14 | AC | 624 ms
52,240 KB |
testcase_15 | AC | 721 ms
56,336 KB |
testcase_16 | AC | 326 ms
34,304 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 44 ms
10,000 KB |
testcase_19 | AC | 634 ms
52,108 KB |
testcase_20 | AC | 669 ms
54,664 KB |
testcase_21 | AC | 352 ms
31,864 KB |
testcase_22 | AC | 148 ms
19,640 KB |
testcase_23 | AC | 621 ms
56,464 KB |
testcase_24 | AC | 98 ms
15,924 KB |
testcase_25 | AC | 8 ms
5,376 KB |
testcase_26 | AC | 2 ms
5,376 KB |
testcase_27 | AC | 2 ms
5,376 KB |
testcase_28 | AC | 2 ms
5,376 KB |
testcase_29 | AC | 2 ms
5,376 KB |
testcase_30 | AC | 2 ms
5,376 KB |
testcase_31 | AC | 2 ms
5,376 KB |
testcase_32 | AC | 2 ms
5,376 KB |
testcase_33 | AC | 2 ms
5,376 KB |
testcase_34 | AC | 2 ms
5,376 KB |
testcase_35 | AC | 2 ms
5,376 KB |
testcase_36 | AC | 2 ms
5,376 KB |
testcase_37 | AC | 2 ms
5,376 KB |
testcase_38 | AC | 2 ms
5,376 KB |
testcase_39 | AC | 2 ms
5,376 KB |
testcase_40 | AC | 2 ms
5,376 KB |
testcase_41 | AC | 2 ms
5,376 KB |
testcase_42 | AC | 2 ms
5,376 KB |
testcase_43 | AC | 2 ms
5,376 KB |
testcase_44 | AC | 2 ms
5,376 KB |
testcase_45 | AC | 2 ms
5,376 KB |
testcase_46 | AC | 2 ms
5,376 KB |
testcase_47 | AC | 2 ms
5,376 KB |
testcase_48 | AC | 2 ms
5,376 KB |
testcase_49 | AC | 2 ms
5,376 KB |
testcase_50 | AC | 2 ms
5,376 KB |
testcase_51 | AC | 2 ms
5,376 KB |
testcase_52 | AC | 2 ms
5,376 KB |
testcase_53 | AC | 2 ms
5,376 KB |
testcase_54 | AC | 2 ms
5,376 KB |
testcase_55 | AC | 2 ms
5,376 KB |
testcase_56 | AC | 2 ms
5,376 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_); 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; #include <unordered_map> void solve() { ll n, m; cin >> n >> m; mint ans = 0; unordered_map<ll, ll> sq; for (ll i = 0; i <= n; ++i) { sq[i * i] = i; } Binomial<mint> binom(n + 1); for (ll y = -n; y <= n; ++y) { if (m + y * y < 0) continue; if (!sq.count(m + y * y)) continue; ll x = sq[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; }