結果
| 問題 | No.2406 Difference of Coordinate Squared |
| ユーザー |
 tonegawa
|
| 提出日時 | 2023-08-04 23:03:57 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 20,065 bytes |
| コンパイル時間 | 2,114 ms |
| コンパイル使用メモリ | 143,240 KB |
| 実行使用メモリ | 15,104 KB |
| 最終ジャッジ日時 | 2024-04-22 21:27:15 |
| 合計ジャッジ時間 | 5,150 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 20 ms
14,920 KB |
| testcase_01 | AC | 31 ms
14,976 KB |
| testcase_02 | AC | 31 ms
14,848 KB |
| testcase_03 | WA | - |
| testcase_04 | AC | 51 ms
14,960 KB |
| testcase_05 | AC | 28 ms
14,976 KB |
| testcase_06 | AC | 30 ms
14,820 KB |
| testcase_07 | AC | 24 ms
14,976 KB |
| testcase_08 | AC | 26 ms
14,848 KB |
| testcase_09 | AC | 83 ms
14,992 KB |
| testcase_10 | AC | 34 ms
15,104 KB |
| testcase_11 | AC | 32 ms
14,924 KB |
| testcase_12 | AC | 30 ms
14,976 KB |
| testcase_13 | AC | 97 ms
14,976 KB |
| testcase_14 | AC | 30 ms
14,976 KB |
| testcase_15 | AC | 29 ms
14,820 KB |
| testcase_16 | AC | 35 ms
14,976 KB |
| testcase_17 | AC | 21 ms
15,012 KB |
| testcase_18 | WA | - |
| testcase_19 | AC | 29 ms
15,044 KB |
| testcase_20 | AC | 35 ms
14,848 KB |
| testcase_21 | AC | 26 ms
15,048 KB |
| testcase_22 | WA | - |
| testcase_23 | AC | 61 ms
14,900 KB |
| testcase_24 | AC | 30 ms
14,848 KB |
| testcase_25 | WA | - |
| testcase_26 | AC | 21 ms
14,848 KB |
| testcase_27 | WA | - |
| testcase_28 | AC | 23 ms
14,976 KB |
| testcase_29 | AC | 24 ms
15,016 KB |
| testcase_30 | AC | 20 ms
14,964 KB |
| testcase_31 | AC | 21 ms
14,892 KB |
| testcase_32 | AC | 20 ms
14,880 KB |
| testcase_33 | AC | 20 ms
14,976 KB |
| testcase_34 | AC | 24 ms
14,956 KB |
| testcase_35 | AC | 22 ms
14,976 KB |
| testcase_36 | AC | 21 ms
14,964 KB |
| testcase_37 | AC | 23 ms
14,976 KB |
| testcase_38 | AC | 21 ms
14,848 KB |
| testcase_39 | WA | - |
| testcase_40 | AC | 20 ms
14,848 KB |
| testcase_41 | AC | 24 ms
14,816 KB |
| testcase_42 | WA | - |
| testcase_43 | AC | 20 ms
14,892 KB |
| testcase_44 | AC | 20 ms
14,976 KB |
| testcase_45 | AC | 25 ms
14,976 KB |
| testcase_46 | AC | 23 ms
14,896 KB |
| testcase_47 | AC | 19 ms
14,976 KB |
| testcase_48 | WA | - |
| testcase_49 | AC | 21 ms
14,956 KB |
| testcase_50 | AC | 19 ms
14,848 KB |
| testcase_51 | AC | 22 ms
14,976 KB |
| testcase_52 | AC | 21 ms
14,900 KB |
| testcase_53 | AC | 20 ms
14,928 KB |
| testcase_54 | AC | 21 ms
14,976 KB |
| testcase_55 | AC | 20 ms
14,976 KB |
| testcase_56 | AC | 20 ms
14,956 KB |
ソースコード
#line 1 ".lib/template.hpp"
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <climits>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#include <thread>
#include <chrono>
#define allof(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)
#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))
#define bit_kth(i, k) ((i >> k)&1)
#define bit_highest(i) (i?63-__builtin_clzll(i):-1)
#define bit_lowest(i) (i?__builtin_ctzll(i):-1)
#define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t))
using ll = long long;
using ld = long double;
using ul = uint64_t;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
using namespace std;
template<typename F, typename S>
std::ostream &operator<<(std::ostream &dest, const std::pair<F, S> &p){
dest << p.first << ' ' << p.second;
return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<std::vector<T>> &v){
int sz = v.size();
if(sz==0) return dest;
for(int i=0;i<sz;i++){
int m = v[i].size();
for(int j=0;j<m;j++) dest << v[i][j] << (i!=sz-1&&j==m-1?'\n':' ');
}
return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<T> &v){
int sz = v.size();
if(sz==0) return dest;
for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
dest << v[sz-1];
return dest;
}
template<typename T, size_t sz>
std::ostream &operator<<(std::ostream &dest, const std::array<T, sz> &v){
if(sz==0) return dest;
for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
dest << v[sz-1];
return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::set<T> &v){
for(auto itr=v.begin();itr!=v.end();){
dest << *itr;
itr++;
if(itr!=v.end()) dest << ' ';
}
return dest;
}
template<typename T, typename E>
std::ostream &operator<<(std::ostream &dest, const std::map<T, E> &v){
for(auto itr=v.begin();itr!=v.end();){
dest << '(' << itr->first << ", " << itr->second << ')';
itr++;
if(itr!=v.end()) dest << '\n';
}
return dest;
}
template<typename T>
vector<T> make_vec(size_t sz, T val){return std::vector<T>(sz, val);}
template<typename T, typename... Tail>
auto make_vec(size_t sz, Tail ...tail){
return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));
}
template<typename T>
vector<T> read_vec(size_t sz){
std::vector<T> v(sz);
for(int i=0;i<(int)sz;i++) std::cin >> v[i];
return v;
}
template<typename T, typename... Tail>
auto read_vec(size_t sz, Tail ...tail){
auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);
for(int i=0;i<(int)sz;i++) v[i] = read_vec<T>(tail...);
return v;
}
void io_init(){
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
}
#line 1 ".lib/math/mod.hpp"
#line 7 ".lib/math/mod.hpp"
#include <type_traits>
#line 9 ".lib/math/mod.hpp"
#include <ostream>
#line 13 ".lib/math/mod.hpp"
// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
struct barrett {
unsigned int _m;
unsigned long long im;
explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
unsigned int umod() const { return _m; }
unsigned int mul(unsigned int a, unsigned int b) const {
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x =
(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned long long y = x * _m;
return (unsigned int)(z - y + (z < y ? _m : 0));
}
};
// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr long long bases[3] = {2, 7, 61};
for (long long a : bases) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);
constexpr int primitive_root_constexpr(int m) {
if (m == 2) return 1;
if (m == 167772161) return 3;
if (m == 469762049) return 3;
if (m == 754974721) return 11;
if (m == 998244353) return 3;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) divs[cnt++] = x;
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
int bsf(unsigned int n) {
return __builtin_ctz(n);
}
// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u;
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
if (m0 < 0) m0 += b / s;
return {s, m0};
}
struct modint_base {};
struct static_modint_base : modint_base {};
template <class T> using is_modint = std::is_base_of<modint_base, T>;
template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;
template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : static_modint_base {
using mint = static_modint;
public:
static constexpr int mod() { return m; }
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
static_modint() : _v(0) {}
template <class T>
static_modint(T v){
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint& operator*=(const mint& rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
if (prime) {
assert(_v);
return pow(umod() - 2);
} else {
auto eg = inv_gcd(_v, m);
assert(eg.first == 1);
return eg.second;
}
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static constexpr unsigned int umod() { return m; }
static constexpr bool prime = is_prime<m>;
};
template <int id> struct dynamic_modint : modint_base {
using mint = dynamic_modint;
public:
static int mod() { return (int)(bt.umod()); }
static void set_mod(int m) {
assert(1 <= m);
bt = barrett(m);
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
dynamic_modint() : _v(0) {}
template <class T>
dynamic_modint(T v) {
long long x = (long long)(v % (long long)(mod()));
if (x < 0) x += mod();
_v = (unsigned int)(x);
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v += mod() - rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator*=(const mint& rhs) {
_v = bt.mul(_v, rhs._v);
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
auto eg = inv_gcd(_v, mod());
assert(eg.first == 1);
return eg.second;
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static barrett bt;
static unsigned int umod() { return bt.umod(); }
};
template <int id> barrett dynamic_modint<id>::bt(998244353);
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;
template <class T>
using is_static_modint = std::is_base_of<static_modint_base, T>;
template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
template <class> struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};
template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
template<int m>
std::ostream &operator<<(std::ostream &dest, const static_modint<m> &a){
dest << a.val();
return dest;
}
template<int id>
std::ostream &operator<<(std::ostream &dest, const dynamic_modint<id> &a){
dest << a.val();
return dest;
}
// 0 <= n < m <= int_max
// 前処理 O(n + log(m))
// 各種計算 O(1)
// 変数 <= n
#line 406 ".lib/math/mod.hpp"
template<typename mint>
struct modcomb{
private:
int n;
std::vector<mint> f, i, fi;
void init(int _n){
assert(0 <= _n && _n < mint::mod());
if(_n < f.size()) return;
n = _n;
f.resize(n + 1), i.resize(n + 1), fi.resize(n + 1);
f[0] = fi[0] = mint(1);
if(n) f[1] = fi[1] = i[1] = mint(1);
for(int j = 2; j <= n; j++) f[j] = f[j - 1] * j;
fi[n] = f[n].inv();
for(int j = n; j >= 2; j--){
fi[j - 1] = fi[j] * j;
i[j] = f[j - 1] * fi[j];
}
}
public:
modcomb(): n(-1){}
modcomb(int _n){
init(_n);
}
void recalc(int _n){
init(std::min(mint::mod() - 1, 1 << ceil_pow2(_n)));
}
mint comb(int a, int b){
if((a < 0) || (b < 0) || (a < b)) return 0;
return f[a] * fi[a - b] * fi[b];
}
mint perm(int a, int b){
if((a < 0) || (b < 0) || (a < b)) return 0;
return f[a] * fi[a - b];
}
mint fac(int x){
assert(0 <= x && x <= n);
return f[x];
}
mint inv(int x){
assert(0 < x && x <= n);
return i[x];
}
mint finv(int x){
assert(0 <= x && x <= n);
return fi[x];
}
};
// mod == 2: 定数時間
// modが素数: O(min(n, mod) + log(n))
template<int id>
struct lucas_prime{
using mint = dynamic_modint<id>;
modcomb<mint> mcb;
void set_mod(int mod){
mint::set_mod(mod);
}
int comb(long long n, long long r){
if(mint::mod() == 1 || n < 0 || r < 0 || n < r) return 0;
if(mint::mod() == 2) return (n & r) == r;
mcb.recalc(std::min(n, (long long)mint::mod()));
mint res = 1;
while(n){
int x = n % mint::mod(), y = r % mint::mod();
res *= mcb.comb(x, y);
n /= mint::mod(), r /= mint::mod();
}
return res.val();
}
};
template<typename mint>
struct modpow_table{
std::vector<mint> v;
// x^maxkまで計算できる
modpow_table(){}
void init(int x, int maxk){
v.resize(maxk + 1);
v[0] = 1;
for(int i = 1; i <= maxk; i++) v[i] = v[i - 1] * x;
}
mint pow(int k){
assert(0 <= k && k < v.size());
return v[k];
}
};
template<int m>
int modpow(long long a, long long b){
int ret = (m == 1 ? 0 : 1), mul = a % m;
while(b){
if(b & 1) ret = ((long long)ret * mul) % m;
mul = ((long long)mul * mul) % m;
b >>= 1;
}
return ret;
}
int modpow(long long a, long long b, int m){
int ret = (m == 1 ? 0 : 1), mul = a % m;
while(b){
if(b & 1) ret = ((long long)ret * mul) % m;
mul = ((long long)mul * mul) % m;
b >>= 1;
}
return ret;
}
#line 514 ".lib/math/mod.hpp"
// modpow(x,2,mod) == aとなるxを返す
// 存在しないなら-1
// mod は素数
long long modsqrt(long long a, long long mod){
a %= mod;
if(a == 0) return 0LL;
if(mod == 2) return 1LL;
if(modpow(a, (mod - 1) / 2, mod) != 1) return -1LL;
if(mod % 4 == 3) return modpow(a, mod / 4 + 1, mod);
long long q = mod - 1, m = 0;
while(q % 2 == 0) q >>= 1, m++;
std::mt19937 mt;
long long z;
do{
z = mt() % mod;
}while(modpow(z, (mod - 1) / 2, mod) != mod - 1);
long long c = modpow(z, q, mod);
long long t = modpow(a, q, mod);
long long r = modpow(a, (q + 1) >> 1, mod);
for(; m > 1; --m) {
long long tmp = modpow(t, 1LL << (m - 2), mod);
if(tmp != 1) r = r * c % mod, t = t * (c * c % mod) % mod;
c = c * c % mod;
}
return r;
}
//n次以下の多項式に対し
//f(0) ~ f(n)を与えf(p)を求める
//O(n log(MOD))
template<typename mint>
mint __lagrange(const std::vector<mint> &y, mint p, modcomb<mint> &mcb){
int sz = y.size();
mcb.recalc(sz);
mint M = 1, res = 0;
std::vector<mint> itable(sz, 1), num(sz);
if(p.val() < sz) return y[p.val()];
for(int i = 0; i < sz; i++){
M *= p - i;
num[i] = p - i;
}
uint32_t cnt = mint::mod() - 2;
while(cnt){
if(cnt & 1){
for(int i = 0; i < sz; i++) itable[i] *= num[i], num[i] *= num[i];
}else{
for(int i = 0; i < sz; i++) num[i] *= num[i];
}
cnt >>= 1;
}
for(int i = 0; i < sz; i++){
mint iQ = mcb.finv(i) * mcb.finv(sz - 1 - i);
if((sz - i - 1) & 1) iQ *= -1;
res += y[i] * iQ * itable[i];
}
return res * M;
}
template<typename mint>
mint lagrange(const std::vector<mint> &y, mint p){
modcomb<mint> mcb;
return __lagrange(y, p, mcb);
}
template<typename mint>
mint riid(mint r, int d, long long n){
if(n == 0) return 0;
if(r.val() == 0){
return d == 0 ? mint(1) : 0;
}
n--;
std::vector<mint> y(d + 2), ipow(d + 2, 1), tbl(d + 2);
for(int i = 0; i < d + 2; i++) tbl[i] = i;
int cnt = d;
while(cnt){
if(cnt & 1){
for(int i = 0; i < d + 2; i++) ipow[i] *= tbl[i], tbl[i] *= tbl[i];
}else{
for(int i = 0; i < d + 2; i++) tbl[i] *= tbl[i];
}
cnt >>= 1;
}
mint tmp = 0, rpow = 1, last = r.pow(n % (mint::mod() - 1));
n %= mint::mod();
for(int i = 0; i < d + 2; i++){
tmp += rpow * ipow[i];
rpow *= r;
y[i] = tmp;
}
modcomb<mint> mcb(y.size());
if(r.val() == 1) return __lagrange<mint>(y, n, mcb);
ipow[0] = 1, ipow[1] = -r;
mint comb = 1, c = 0;
for(int i = 2; i < d + 2; i++) ipow[i] = ipow[i - 1] * ipow[1];
for(int i = 0; i < d + 1; i++){
comb *= mcb.inv(i + 1) * mint(d + 1 - i);
c += comb * ipow[d - i] * y[i];
}
mint di = mint(1 - r);
c *= di.pow(d + 1).inv();
mint powerRinv = 1, rinv = r.inv();
for(int i = 0; i < d + 1; i++){
y[i] -= c;
y[i] *= powerRinv;
powerRinv *= rinv;
}
y.pop_back();
return c + last * __lagrange<mint>(y, n, mcb);
}
#line 3 "c.cpp"
using mint = modint998244353;
int main(){
io_init();
modcomb<mint> mcb(1000000);
mint ans = 0;
ll n, m;
std::cin >> n >> m;
if(m == 0){
if(n & 1){
std::cout << 0 << '\n';
}else{
for(ll yoko = 0; yoko <= n; yoko += 2){
ll tate = n - yoko;
ans += mcb.comb(n, yoko) * mcb.comb(yoko, yoko / 2) * mcb.comb(tate, tate / 2);
}
std::cout << (ans / mint(4).pow(n)) << '\n';
}
return 0;
}
if(m < 0) m *= -1;
for(ll i = 1; i * i <= m; i++){
if(m % i != 0) continue;
ll j = m / i;
if(i % 2 != j % 2) continue;
// x - y = i && x + y = j
// x = (j + i) / 2
// y = (j - i) / 2
ll x = (j + i) / 2;
ll y = (j - i) / 2;
if(x + y > n || (x + y) % 2 != n % 2) continue;
mint tmp = 0;
// (+-x, +-y) 4パターン
// (x, y) を求めて × 4
for(ll yoko = x; yoko <= n - y; yoko += 2){
ll tate = n - yoko;
//std::cout << mcb.comb(n, yoko) << " " << mcb.comb(yoko, x) << '\n';
tmp += mcb.comb(n, yoko) * mcb.comb(yoko, (yoko - x) / 2) * mcb.comb(tate, (tate - y) / 2);
}
if(y == 0) tmp *= 2;
else tmp *= 4;
ans += tmp;
}
std::cout << (ans / mint(4).pow(n)) << '\n';
}