提出 #29302605

---

ソースコード 拡げる

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <unordered_map>
#include <map>
#include <string>
#include <deque>
#include <bitset>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <atcoder/all>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, ll> Pl;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vl;
typedef vector<vector<long long>> vvl;
typedef vector<P> vp;
typedef vector<Pl> vpl;
static const long long LINF = (ll)(1e18+99);
static const int INF = 1e9+99;

#define OVERLOAD2(_1,_2,name,...) name 
#define OVERLOAD3(_1,_2,_3,name,...) name
#define OVERLOAD4(_1,_2,_3,_4,name,...) name
#define OVERLOAD5(_1,_2,_3,_4,_5,name,...) name
#define OVERLOAD6(_1,_2,_3,_4,_5,_6,name,...) name
#define REP2(i, a, b) for (long long i = (a), _n = (b); i < _n; i++)
#define REP1(i, a) for(long long i = 0, _n = (a); i < _n; i++)
#define rep(...) OVERLOAD3(__VA_ARGS__,REP2,REP1)(__VA_ARGS__)
#define per(i, a, b) for (long long i = (b)-1, _n = (a); i >= _n; i--)
#define pb emplace_back
#define mp make_pair
#define bg begin()
#define en end()
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define sz(v) (int)(v).size()
#define iota(v) iota(v.begin(), v.end(), 0)
#define mul(x, y) __builtin_smulll_overflow((x), (y), &(x))
#define pnt(x) __builtin_popcountll((x))
#define EXIT(x) {cout << (x) << "\n"; return 0;}
#define SUM(type,v) accumulate((v).begin(), (v).end(), (type)0)
#define MIN(v) *min_element((v).begin(), (v).end())
#define MAX(v) *max_element((v).begin(), (v).end())
#define UNI(v) (v).erase(unique((v).begin(), (v).end()), (v).end())
#define REV(v) reverse((v).begin(), (v.end()))
#define INT(...) int __VA_ARGS__; in(__VA_ARGS__)
#define LL(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__; in(__VA_ARGS__)
#define VECTOR1(type,name) vector<type>name
#define VECTOR2(type,name,size) vector<type>name(size)
#define VECTOR3(type,name,size,val) vector<type>name(size,val)
#define VECTOR(...) OVERLOAD4(__VA_ARGS__, VECTOR3, VECTOR2, VECTOR1)(__VA_ARGS__)
#define VEC(type,name,size) VECTOR2(type,name,size); in(name)
#define VV1(type,name) vector<vector<type>>name
#define VV2(type,name,h) vector<vector<type>>name(h,vector<type>)
#define VV3(type,name,h,w) vector<vector<type>>name(h,vector<type>(w))
#define VV4(type,name,h,w,val) vector<vector<type>>name(h,vector<type>(w,val))
#define VV(...) OVERLOAD5(__VA_ARGS__,VV4,VV3,VV2,VV1)(__VA_ARGS__)


#ifdef DEBUG_
#define dump(x)\
    cout<<string(#x)<<":";\
    cout<<"["<<to_string(__LINE__)<<":"<<__FUNCTION__<<"]"<<endl;\
    cout<<x<<"\n\n";
#define dumps(...) cout<<"  "; \
cout<<#__VA_ARGS__<<" :["<<__LINE__<<":"<<__FUNCTION__<<"]"<<endl; \
cout<<"    "; \
dump_func(__VA_ARGS__)
#else 
#define dump(x) void(0);
#define dumps(...) void(0);
#endif

//istream
template<typename T1, typename T2>istream& operator>>(istream& i, pair<T1, T2> &v) {return i >> v.fi >> v.se;}
template<typename T>istream& operator>>(istream& i, vector<T> &v) {rep(j, sz(v)) i >> v[j]; return i;}

//debug
#ifdef DEBUG_
template<typename T> string _out(T &x) {if (x==INF || x==LINF) {return "inf";} else if (x==-INF || x==-LINF) {return "-inf";} else {return to_string(x);}}

void dump_func() {cout<<endl;}
template <class T, class... U>void dump_func(T&& t, U&&... u) {cout<<t;if (sizeof...(u)==0) {cout << " "; } else {cout << ", ";}dump_func(std::move(u)...);}
#else
template<typename T> string _out(T &x) { return to_string(x); }
#endif

template<typename T, typename U> ostream& operator<<(ostream& o, map<T, U> m) { for (auto x : m) o<<"["<<_out(x.fi)<<"->"<<_out(x.se)<<"], "; return o;}
template<typename T> ostream& operator<<(ostream& o, set<T> st) { o<<"<";for (auto i = st.bg; i!=st.en; i++) { if (i!=st.bg) o<<","; o<<setw(3)<<_out(*i);}o<<">"; return o;}
template<typename T, typename U> ostream& operator<<(ostream& o, pair<T, U> pr) { o<<"("<<_out(pr.fi)<<", "<<_out(pr.se)<<")"; return o;}
template<typename T, typename U> ostream& operator<<(ostream& o, vector<map<T, U>> v) { rep(i, sz(v)) { o<<v[i]; o<<"\n";} return o; }
template<typename T> ostream& operator<<(ostream& o, vector<set<T>> v) {rep(i, sz(v)) { o<<v[i];o<<"\n";} return o; }

template<typename T, typename U> ostream& operator<<(ostream& o, vector<pair<T, U>> v) { o<<"{"; rep(i, sz(v)) { if (i>0) o<<","; o<<setw(3)<<v[i];} o<<"}\n";return o;}
template<typename T> ostream& operator<<(ostream& o, vector<T> v) {o<<"{"; rep(i, sz(v)) { if (i>0) o<<","; o<<setw(3)<<_out(v[i]); } o<<"}\n";return o;}

template<typename T>ostream& operator<<(ostream& o, vector<vector<T>> &v) { rep(i, sz(v)) { o<<v[i]; } o<<"\n"; return o; }
template<typename T, typename U> ostream& operator<<(ostream& o, vector<vector<pair<T, U>>> &v) { rep(i, sz(v)) { o<<v[i]<<"\n"; } o<<"\n"; return o; }

//Change
template<typename T> bool chmax(T &x, T y) {if(x<y){swap(x, y); return true;} return false;}
template<typename T> bool chmin(T &x, T y) {if(x>y){swap(x, y); return true;} return false;}

//input output
inline void in() {}
template <typename T, class... U> void in(T &t, U &... u) { cin >> t; in(u...); }
inline void out() {}
template <typename T, class... U> void out(T &t, U &... u) { cout << t << "\n"; out(u...); }

//Other Func
template<typename T> vector<T> mkrui(vector<T>& v) {vector<T> res(sz(v)+1, 0); rep(i,sz(v)) res[i+1] = res[i]+v[i]; return res;}
template<typename T> T Abs(T a) { if (a<0) return -a; return a; }
template<typename T> T Floor(T a, T b) {if ((a<0 && b<0) || (a>0 && b>0)) return a/b;else return (Abs(a)+Abs(b)-1)/Abs(b)*-1LL;}
template<typename T> T Ceil(T a, T b) { if ((a<0 && b<0) || (a>0 && b>0)) return (Abs(a)+Abs(b)-1)/Abs(b);return a/b;}
long long bit(long long S, long long i) { return (S>>i)&1LL;}

template <typename Cost>
struct Edge { 
    int from, to, id;
    Cost cost;
    Edge(int from = -1, int to = -1, int id = -1, Cost cost = 1) : from(from), to(to), id(id), cost(cost) {}
    bool operator< (const Edge &e) const {return cost < e.cost;}
    bool operator> (const Edge &e) const {return cost > e.cost;}
    operator int() const { return to; }
};

template <typename Cost>
struct Graph : vector<vector<Edge<Cost>>>{
    Graph(int n = 0) : vector<vector<Edge<Cost>>>(n) {}
    void add_edge(int s, int t, int id = -1, Cost cost = 1) {(*this)[s].emplace_back(s,t,id,cost);}
};
/*
int di[4] = {-1, 1, 0, 0}, dj[4] = {0, 0, -1, 1};
*/

using namespace atcoder;
//using mint = modint1000000007;
using mint = modint998244353;
//using mint = modint;
const int MAX = 2000005;
static const long long MOD = 1000000007;

unordered_map<ll, mint> memo;

mint dfs(ll x) {
    if (memo.count(x)) return memo[x];
    mint res = 1;
    if (x>=4) res = dfs(Ceil(x,2LL)) * dfs(Floor(x,2LL));
    else res = x;
    return memo[x] = res;
}

int main(void) {
    LL(X);
    mint a = dfs(X);
    ll ans = a.val();
    out(ans);
    

    return 0;
}

提出情報

ジャッジ結果