結果
問題 |
No.3089 Base M Numbers, But Only 0~9
|
ユーザー |
|
提出日時 | 2025-04-04 23:09:47 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 78 ms / 2,000 ms |
コード長 | 31,932 bytes |
コンパイル時間 | 1,496 ms |
コンパイル使用メモリ | 136,104 KB |
実行使用メモリ | 5,888 KB |
最終ジャッジ日時 | 2025-04-04 23:09:50 |
合計ジャッジ時間 | 3,255 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 19 |
ソースコード
#include <iomanip> #include <optional> #include <ostream> #include <numeric> #include <unordered_set> #include <iostream> #include <unordered_map> #include <functional> #include <cassert> #include <stack> #include <vector> #include <bitset> #include <algorithm> #include <iterator> #include <map> #include <queue> #include <deque> #include <istream> #include <fstream> #include <utility> #include <array> #include <string> #include <set> #include <type_traits> #ifndef KK2_TEMPLATE_PROCON_HPP #define KK2_TEMPLATE_PROCON_HPP 1 #ifndef KK2_TEMPLATE_CONSTANT_HPP #define KK2_TEMPLATE_CONSTANT_HPP 1 #ifndef KK2_TEMPLATE_TYPE_ALIAS_HPP #define KK2_TEMPLATE_TYPE_ALIAS_HPP 1 using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; using pi = std::pair<int, int>; using pl = std::pair<i64, i64>; using pil = std::pair<int, i64>; using pli = std::pair<i64, int>; template <class T> using vc = std::vector<T>; template <class T> using vvc = std::vector<vc<T>>; template <class T> using vvvc = std::vector<vvc<T>>; template <class T> using vvvvc = std::vector<vvvc<T>>; template <class T> using pq = std::priority_queue<T>; template <class T> using pqi = std::priority_queue<T, std::vector<T>, std::greater<T>>; #endif // KK2_TEMPLATE_TYPE_ALIAS_HPP template <class T> constexpr T infty = 0; template <> constexpr int infty<int> = (1 << 30) - 123; template <> constexpr i64 infty<i64> = (1ll << 62) - (1ll << 31); template <> constexpr i128 infty<i128> = (i128(1) << 126) - (i128(1) << 63); template <> constexpr u32 infty<u32> = infty<int>; template <> constexpr u64 infty<u64> = infty<i64>; template <> constexpr u128 infty<u128> = infty<i128>; template <> constexpr double infty<double> = infty<i64>; template <> constexpr long double infty<long double> = infty<i64>; constexpr int mod = 998244353; constexpr int modu = 1e9 + 7; constexpr long double PI = 3.14159265358979323846; #endif // KK2_TEMPLATE_CONSTANT_HPP #ifndef KK2_TEMPLATE_FUNCTION_UTIL_HPP #define KK2_TEMPLATE_FUNCTION_UTIL_HPP 1 namespace kk2 { template <class T, class... Sizes> auto make_vector(int first, Sizes... sizes) { if constexpr (sizeof...(sizes) == 0) { return std::vector<T>(first); } else { return std::vector<decltype(make_vector<T>(sizes...))>(first, make_vector<T>(sizes...)); } } template <class T, class U> void fill_all(std::vector<T> &v, const U &x) { std::fill(std::begin(v), std::end(v), T(x)); } template <class T, class U> void fill_all(std::vector<std::vector<T>> &v, const U &x) { for (auto &u : v) fill_all(u, x); } template <class C> int mysize(const C &c) { return size(c); } // T: comutative monoid template <class T, class U> U all_sum(const std::vector<T> &v, U unit = U()) { U res = unit; for (const auto &x : v) res += x; return res; } template <class T, class U> U all_sum(const std::vector<std::vector<T>> &v, U unit = U()) { U res = U(); for (const auto &u : v) res += all_sum(u, unit); return res; } // T: commutative monoid, F: (U, T) -> U template <class T, class U, class F> U all_prod(const std::vector<T> &v, U init, const F &f, U = U()) { U res = init; for (const auto &x : v) res = f(res, x); return res; } template <class T, class U, class F> U all_prod(const std::vector<std::vector<T>> &v, U init, const F &f, U unit) { U res = init; for (const auto &u : v) res = f(res, all_prod(u, unit, f, unit)); return res; } template <class T> T all_min(const std::vector<T> &v) { if (v.empty()) return T(); T res = v[0]; for (const auto &x : v) res = res > x ? x : res; return res; } template <class T> T all_min(const std::vector<std::vector<T>> &v) { T res{}; bool first = true; for (const auto &u : v) { if (u.empty()) continue; if (first) { res = all_min(u); first = false; } else { T tmp = all_min(u); res = res > tmp ? tmp : res; } } return res; } template <class T> T all_max(const std::vector<T> &v) { if (v.empty()) return T(); T res = v[0]; for (const auto &x : v) res = res < x ? x : res; return res; } template <class T> T all_max(const std::vector<std::vector<T>> &v) { T res{}; bool first = true; for (const auto &u : v) { if (u.empty()) continue; if (first) { res = all_max(u); first = false; } else { T tmp = all_max(u); res = res < tmp ? tmp : res; } } return res; } } // namespace kk2 #endif // KK2_TEMPLATE_FUNCTION_UTIL_HPP #ifndef KK2_TEMPLATE_IO_UTIL_HPP #define KK2_TEMPLATE_IO_UTIL_HPP 1 #ifndef KK2_TYPE_TRAITS_TYPE_TRAITS_HPP #define KK2_TYPE_TRAITS_TYPE_TRAITS_HPP 1 namespace kk2 { #ifndef _MSC_VER template <typename T> using is_signed_int128 = typename std::conditional<std::is_same<T, __int128_t>::value or std::is_same<T, __int128>::value, std::true_type, std::false_type>::type; template <typename T> using is_unsigned_int128 = typename std::conditional<std::is_same<T, __uint128_t>::value or std::is_same<T, unsigned __int128>::value, std::true_type, std::false_type>::type; template <typename T> using is_integral = typename std::conditional<std::is_integral<T>::value or is_signed_int128<T>::value or is_unsigned_int128<T>::value, std::true_type, std::false_type>::type; template <typename T> using is_signed = typename std::conditional<std::is_signed<T>::value or is_signed_int128<T>::value, std::true_type, std::false_type>::type; template <typename T> using is_unsigned = typename std::conditional<std::is_unsigned<T>::value or is_unsigned_int128<T>::value, std::true_type, std::false_type>::type; template <typename T> using make_unsigned_int128 = typename std::conditional<std::is_same<T, __int128_t>::value, __uint128_t, unsigned __int128>; template <typename T> using to_unsigned = typename std::conditional<is_signed_int128<T>::value, make_unsigned_int128<T>, typename std::conditional<std::is_signed<T>::value, std::make_unsigned<T>, std::common_type<T>>::type>::type; #else template <typename T> using is_integral = std::enable_if_t<std::is_integral<T>::value>; template <typename T> using is_signed = std::enable_if_t<std::is_signed<T>::value>; template <typename T> using is_unsigned = std::enable_if_t<std::is_unsigned<T>::value>; template <typename T> using to_unsigned = std::make_unsigned<T>; #endif // _MSC_VER template <typename T> using is_integral_t = std::enable_if_t<is_integral<T>::value>; template <typename T> using is_signed_t = std::enable_if_t<is_signed<T>::value>; template <typename T> using is_unsigned_t = std::enable_if_t<is_unsigned<T>::value>; template <typename T> using is_function_pointer = typename std::conditional<std::is_pointer_v<T> && std::is_function_v<std::remove_pointer_t<T>>, std::true_type, std::false_type>::type; template <typename T, std::enable_if_t<is_function_pointer<T>::value> * = nullptr> struct is_two_args_function_pointer : std::false_type {}; template <typename R, typename T1, typename T2> struct is_two_args_function_pointer<R (*)(T1, T2)> : std::true_type {}; template <typename T> using is_two_args_function_pointer_t = std::enable_if_t<is_two_args_function_pointer<T>::value>; namespace type_traits { struct istream_tag {}; struct ostream_tag {}; } // namespace type_traits template <typename T> using is_standard_istream = typename std::conditional<std::is_same<T, std::istream>::value || std::is_same<T, std::ifstream>::value, std::true_type, std::false_type>::type; template <typename T> using is_standard_ostream = typename std::conditional<std::is_same<T, std::ostream>::value || std::is_same<T, std::ofstream>::value, std::true_type, std::false_type>::type; template <typename T> using is_user_defined_istream = std::is_base_of<type_traits::istream_tag, T>; template <typename T> using is_user_defined_ostream = std::is_base_of<type_traits::ostream_tag, T>; template <typename T> using is_istream = typename std::conditional<is_standard_istream<T>::value || is_user_defined_istream<T>::value, std::true_type, std::false_type>::type; template <typename T> using is_ostream = typename std::conditional<is_standard_ostream<T>::value || is_user_defined_ostream<T>::value, std::true_type, std::false_type>::type; template <typename T> using is_istream_t = std::enable_if_t<is_istream<T>::value>; template <typename T> using is_ostream_t = std::enable_if_t<is_ostream<T>::value>; } // namespace kk2 #endif // KK2_TYPE_TRAITS_TYPE_TRAITS_HPP // なんかoj verifyはプロトタイプ宣言が落ちる namespace impl { struct read { template <class IStream, class T> inline static void all_read(IStream &is, T &x) { is >> x; } template <class IStream, class T, class U> inline static void all_read(IStream &is, std::pair<T, U> &p) { all_read(is, p.first); all_read(is, p.second); } template <class IStream, class T> inline static void all_read(IStream &is, std::vector<T> &v) { for (T &x : v) all_read(is, x); } template <class IStream, class T, size_t F> inline static void all_read(IStream &is, std::array<T, F> &a) { for (T &x : a) all_read(is, x); } }; struct write { template <class OStream, class T> inline static void all_write(OStream &os, const T &x) { os << x; } template <class OStream, class T, class U> inline static void all_write(OStream &os, const std::pair<T, U> &p) { all_write(os, p.first); all_write(os, ' '); all_write(os, p.second); } template <class OStream, class T> inline static void all_write(OStream &os, const std::vector<T> &v) { for (int i = 0; i < (int)v.size(); ++i) { if (i) all_write(os, ' '); all_write(os, v[i]); } } template <class OStream, class T, size_t F> inline static void all_write(OStream &os, const std::array<T, F> &a) { for (int i = 0; i < (int)F; ++i) { if (i) all_write(os, ' '); all_write(os, a[i]); } } }; } // namespace impl template <class IStream, class T, class U, kk2::is_istream_t<IStream> * = nullptr> IStream &operator>>(IStream &is, std::pair<T, U> &p) { impl::read::all_read(is, p); return is; } template <class IStream, class T, kk2::is_istream_t<IStream> * = nullptr> IStream &operator>>(IStream &is, std::vector<T> &v) { impl::read::all_read(is, v); return is; } template <class IStream, class T, size_t F, kk2::is_istream_t<IStream> * = nullptr> IStream &operator>>(IStream &is, std::array<T, F> &a) { impl::read::all_read(is, a); return is; } template <class OStream, class T, class U, kk2::is_ostream_t<OStream> * = nullptr> OStream &operator<<(OStream &os, const std::pair<T, U> &p) { impl::write::all_write(os, p); return os; } template <class OStream, class T, kk2::is_ostream_t<OStream> * = nullptr> OStream &operator<<(OStream &os, const std::vector<T> &v) { impl::write::all_write(os, v); return os; } template <class OStream, class T, size_t F, kk2::is_ostream_t<OStream> * = nullptr> OStream &operator<<(OStream &os, const std::array<T, F> &a) { impl::write::all_write(os, a); return os; } #endif // KK2_TEMPLATE_IO_UTIL_HPP #ifndef KK2_TEMPLATE_MACROS_HPP #define KK2_TEMPLATE_MACROS_HPP 1 #define rep1(a) for (long long _ = 0; _ < (long long)(a); ++_) #define rep2(i, a) for (long long i = 0; i < (long long)(a); ++i) #define rep3(i, a, b) for (long long i = (a); i < (long long)(b); ++i) #define repi2(i, a) for (long long i = (a) - 1; i >= 0; --i) #define repi3(i, a, b) for (long long i = (a) - 1; i >= (long long)(b); --i) #define overload3(a, b, c, d, ...) d #define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define repi(...) overload3(__VA_ARGS__, repi3, repi2, rep1)(__VA_ARGS__) #define fi first #define se second #define all(p) begin(p), end(p) #endif // KK2_TEMPLATE_MACROS_HPP struct FastIOSetUp { FastIOSetUp() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } fast_io_set_up; auto &kin = std::cin; auto &kout = std::cout; auto (*kendl)(std::ostream &) = std::endl<char, std::char_traits<char>>; void Yes(bool b = 1) { kout << (b ? "Yes\n" : "No\n"); } void No(bool b = 1) { kout << (b ? "No\n" : "Yes\n"); } void YES(bool b = 1) { kout << (b ? "YES\n" : "NO\n"); } void NO(bool b = 1) { kout << (b ? "NO\n" : "YES\n"); } void yes(bool b = 1) { kout << (b ? "yes\n" : "no\n"); } void no(bool b = 1) { kout << (b ? "no\n" : "yes\n"); } template <class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); } template <class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); } std::istream &operator>>(std::istream &is, u128 &x) { std::string s; is >> s; x = 0; for (char c : s) { assert('0' <= c && c <= '9'); x = x * 10 + c - '0'; } return is; } std::istream &operator>>(std::istream &is, i128 &x) { std::string s; is >> s; bool neg = s[0] == '-'; x = 0; for (int i = neg; i < (int)s.size(); i++) { assert('0' <= s[i] && s[i] <= '9'); x = x * 10 + s[i] - '0'; } if (neg) x = -x; return is; } std::ostream &operator<<(std::ostream &os, u128 x) { if (x == 0) return os << '0'; std::string s; while (x) { s.push_back('0' + x % 10); x /= 10; } std::reverse(s.begin(), s.end()); return os << s; } std::ostream &operator<<(std::ostream &os, i128 x) { if (x == 0) return os << '0'; if (x < 0) { os << '-'; x = -x; } std::string s; while (x) { s.push_back('0' + x % 10); x /= 10; } std::reverse(s.begin(), s.end()); return os << s; } #endif // KK2_TEMPLATE_PROCON_HPP #ifndef KK2_TEMPLATE_DEBUG_HPP #define KK2_TEMPLATE_DEBUG_HPP 1 #ifndef KK2_TYPE_TRAITS_MEMBER_HPP #define KK2_TYPE_TRAITS_MEMBER_HPP 1 namespace kk2 { #define HAS_MEMBER_FUNC(member) \ template <typename T, typename... Ts> struct has_member_func_##member##_impl { \ template <typename U> \ static std::true_type check(decltype(std::declval<U>().member(std::declval<Ts>()...)) *); \ template <typename U> static std::false_type check(...); \ using type = decltype(check<T>(nullptr)); \ }; \ template <typename T, typename... Ts> \ struct has_member_func_##member : has_member_func_##member##_impl<T, Ts...>::type {}; \ template <typename T, typename... Ts> \ using has_member_func_##member##_t = \ std::enable_if_t<has_member_func_##member<T, Ts...>::value>; \ template <typename T, typename... Ts> \ using not_has_member_func_##member##_t = \ std::enable_if_t<!has_member_func_##member<T, Ts...>::value>; #define HAS_MEMBER_VAR(member) \ template <typename T> struct has_member_var_##member##_impl { \ template <typename U> static std::true_type check(decltype(std::declval<U>().member) *); \ template <typename U> static std::false_type check(...); \ using type = decltype(check<T>(nullptr)); \ }; \ template <typename T> \ struct has_member_var_##member : has_member_var_##member##_impl<T>::type {}; \ template <typename T> \ using has_member_var_##member##_t = std::enable_if_t<has_member_var_##member<T>::value>; \ template <typename T> \ using not_has_member_var_##member##_t = std::enable_if_t<!has_member_var_##member<T>::value>; HAS_MEMBER_FUNC(debug_output) HAS_MEMBER_FUNC(val) #undef HAS_MEMBER_FUNC #undef HAS_MEMBER_VAR } // namespace kk2 #endif // KK2_TYPE_TRAITS_MEMBER_HPP namespace kk2 { namespace debug { #ifdef KK2 template <class OStream, is_ostream_t<OStream> *> void output(OStream &os); template <class OStream, class T, is_ostream_t<OStream> *> void output(OStream &os, const T &t); template <class OStream, class T, is_ostream_t<OStream> *> void output(OStream &os, const std::vector<T> &v); template <class OStream, class T, is_ostream_t<OStream> *> void output(OStream &os, const std::vector<std::vector<T>> &d); template <class OStream, class T, size_t F, is_ostream_t<OStream> *> void output(OStream &os, const std::array<T, F> &a); template <class OStream, class T, class U, is_ostream_t<OStream> *> void output(OStream &os, const std::pair<T, U> &p); template <class OStream, class T, is_ostream_t<OStream> *> void output(OStream &os, const std::queue<T> &q); template <class OStream, class T, class Container, class Compare, is_ostream_t<OStream> *> void output(OStream &os, const std::priority_queue<T, Container, Compare> &q); template <class OStream, class T, is_ostream_t<OStream> *> void output(OStream &os, const std::deque<T> &d); template <class OStream, class T, is_ostream_t<OStream> *> void output(OStream &os, const std::stack<T> &s); template <class OStream, class Key, class Compare, class Allocator, is_ostream_t<OStream> *> void output(OStream &os, const std::set<Key, Compare, Allocator> &s); template <class OStream, class Key, class Compare, class Allocator, is_ostream_t<OStream> *> void output(OStream &os, const std::multiset<Key, Compare, Allocator> &s); template <class OStream, class Key, class Hash, class KeyEqual, class Allocator, is_ostream_t<OStream> *> void output(OStream &os, const std::unordered_set<Key, Hash, KeyEqual, Allocator> &s); template <class OStream, class Key, class Hash, class KeyEqual, class Allocator, is_ostream_t<OStream> *> void output(OStream &os, const std::unordered_multiset<Key, Hash, KeyEqual, Allocator> &s); template <class OStream, class Key, class T, class Compare, class Allocator, is_ostream_t<OStream> *> void output(OStream &os, const std::map<Key, T, Compare, Allocator> &m); template <class OStream, class Key, class T, class Hash, class KeyEqual, class Allocator, is_ostream_t<OStream> *> void output(OStream &os, const std::unordered_map<Key, T, Hash, KeyEqual, Allocator> &m); template <class OStream, is_ostream_t<OStream> * = nullptr> void output(OStream &) { } template <class OStream, class T, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const T &t) { if constexpr (has_member_func_debug_output<T, OStream &>::value) { t.debug_output(os); } else { os << t; } } template <class OStream, class T, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::vector<T> &v) { os << "["; for (int i = 0; i < (int)v.size(); i++) { output(os, v[i]); if (i + 1 != (int)v.size()) os << ", "; } os << "]"; } template <class OStream, class T, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::vector<std::vector<T>> &d) { os << "[\n"; for (int i = 0; i < (int)d.size(); i++) { output(os, d[i]); output(os, "\n"); } os << "]"; } template <class OStream, class T, size_t F, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::array<T, F> &a) { os << "["; for (int i = 0; i < (int)F; i++) { output(os, a[i]); if (i + 1 != (int)F) os << ", "; } os << "]"; } template <class OStream, class T, class U, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::pair<T, U> &p) { os << "("; output(os, p.first); os << ", "; output(os, p.second); os << ")"; } template <class OStream, class T, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::queue<T> &q) { os << "["; std::queue<T> tmp = q; while (!tmp.empty()) { output(os, tmp.front()); tmp.pop(); if (!tmp.empty()) os << ", "; } os << "]"; } template <class OStream, class T, class Container, class Compare, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::priority_queue<T, Container, Compare> &q) { os << "["; std::priority_queue<T, Container, Compare> tmp = q; while (!tmp.empty()) { output(os, tmp.top()); tmp.pop(); if (!tmp.empty()) os << ", "; } os << "]"; } template <class OStream, class T, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::deque<T> &d) { os << "["; std::deque<T> tmp = d; while (!tmp.empty()) { output(os, tmp.front()); tmp.pop_front(); if (!tmp.empty()) os << ", "; } os << "]"; } template <class OStream, class T, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::stack<T> &s) { os << "["; std::stack<T> tmp = s; std::vector<T> v; while (!tmp.empty()) { v.push_back(tmp.top()); tmp.pop(); } for (int i = (int)v.size() - 1; i >= 0; i--) { output(os, v[i]); if (i != 0) os << ", "; } os << "]"; } template <class OStream, class Key, class Compare, class Allocator, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::set<Key, Compare, Allocator> &s) { os << "{"; std::set<Key, Compare, Allocator> tmp = s; for (auto it = tmp.begin(); it != tmp.end(); ++it) { output(os, *it); if (std::next(it) != tmp.end()) os << ", "; } os << "}"; } template <class OStream, class Key, class Compare, class Allocator, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::multiset<Key, Compare, Allocator> &s) { os << "{"; std::multiset<Key, Compare, Allocator> tmp = s; for (auto it = tmp.begin(); it != tmp.end(); ++it) { output(os, *it); if (std::next(it) != tmp.end()) os << ", "; } os << "}"; } template <class OStream, class Key, class Hash, class KeyEqual, class Allocator, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::unordered_set<Key, Hash, KeyEqual, Allocator> &s) { os << "{"; std::unordered_set<Key, Hash, KeyEqual, Allocator> tmp = s; for (auto it = tmp.begin(); it != tmp.end(); ++it) { output(os, *it); if (std::next(it) != tmp.end()) os << ", "; } os << "}"; } template <class OStream, class Key, class Hash, class KeyEqual, class Allocator, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::unordered_multiset<Key, Hash, KeyEqual, Allocator> &s) { os << "{"; std::unordered_multiset<Key, Hash, KeyEqual, Allocator> tmp = s; for (auto it = tmp.begin(); it != tmp.end(); ++it) { output(os, *it); if (std::next(it) != tmp.end()) os << ", "; } os << "}"; } template <class OStream, class Key, class T, class Compare, class Allocator, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::map<Key, T, Compare, Allocator> &m) { os << "{"; std::map<Key, T, Compare, Allocator> tmp = m; for (auto it = tmp.begin(); it != tmp.end(); ++it) { output(os, it->first); os << ": "; output(os, it->second); if (std::next(it) != tmp.end()) os << ", "; } os << "}"; } template <class OStream, class Key, class T, class Hash, class KeyEqual, class Allocator, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::unordered_map<Key, T, Hash, KeyEqual, Allocator> &m) { os << "{"; std::unordered_map<Key, T, Hash, KeyEqual, Allocator> tmp = m; for (auto it = tmp.begin(); it != tmp.end(); ++it) { output(os, it->first); os << ": "; output(os, it->second); if (std::next(it) != tmp.end()) os << ", "; } os << "}"; } template <class OStream, class T, class... Args, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const T &t, const Args &...args) { output(os, t); os << ' '; output(os, args...); } template <class OStream, is_ostream_t<OStream> * = nullptr> void outputln(OStream &os) { os << '\n'; os.flush(); } template <class OStream, class T, class... Args, is_ostream_t<OStream> * = nullptr> void outputln(OStream &os, const T &t, const Args &...args) { output(os, t, args...); os << '\n'; os.flush(); } #else template <class OStream, class... Args, is_ostream_t<OStream> * = nullptr> void output(OStream &, const Args &...) { } template <class OStream, class... Args, is_ostream_t<OStream> * = nullptr> void outputln(OStream &, const Args &...) { } #endif // KK2 } // namespace debug } // namespace kk2 #endif // KK2_TEMPLATE_DEBUG_HPP #ifndef KK2_MODINT_MODINT_HPP #define KK2_MODINT_MODINT_HPP 1 namespace kk2 { template <int p> struct ModInt { using mint = ModInt; public: static int Mod; constexpr static unsigned int getmod() { if (p > 0) return p; else return Mod; } static void setmod(int Mod_) { assert(1 <= Mod_); Mod = Mod_; } static mint raw(int v) { mint x; x._v = v; return x; } constexpr ModInt() : _v(0) {} template <class T, is_integral_t<T> * = nullptr> constexpr ModInt(T v) { if constexpr (is_signed<T>::value) { v = v % (long long)(getmod()); if (v < 0) v += getmod(); _v = v; } else if constexpr (is_unsigned<T>::value) { _v = v %= getmod(); } else { ModInt(); } } unsigned int val() const { return _v; } mint &operator++() { _v++; if (_v == getmod()) _v = 0; return *this; } mint &operator--() { if (_v == 0) _v = getmod(); _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 >= getmod()) _v -= getmod(); return *this; } mint &operator-=(const mint &rhs) { _v += getmod() - rhs._v; if (_v >= getmod()) _v -= getmod(); return *this; } mint &operator*=(const mint &rhs) { unsigned long long z = _v; z *= rhs._v; z %= getmod(); _v = z; 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; n %= (long long)getmod() - 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; } mint inv() const { long long s = getmod(), t = _v; long long m0 = 0, m1 = 1; while (t) { long long u = s / t; s -= t * u; m0 -= m1 * u; std::swap(s, t); std::swap(m0, m1); } if (m0 < 0) m0 += getmod() / s; return m0; } 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; } template <class OStream, is_ostream_t<OStream> * = nullptr> friend OStream &operator<<(OStream &os, const mint &mint_) { os << mint_._v; return os; } template <class IStream, is_istream_t<IStream> * = nullptr> friend IStream &operator>>(IStream &is, mint &mint_) { long long x; is >> x; mint_ = mint(x); return is; } private: unsigned int _v; }; template <int p> int ModInt<p>::Mod = 998244353; using mint998 = ModInt<998244353>; using mint107 = ModInt<1000000007>; } // namespace kk2 #endif // KK2_MODINT_MODINT_HPP using namespace std; void solve() { i64 m; kin >> m; string s; kin >> s; kk2::mint998 res = 0; kk2::mint998 pw = 1; vc<kk2::mint998> count(s.size()), sum(s.size()); repi (i, s.size()) { int j = s[i] - '0'; count[i] = (m - 1 - j) / 10 + 1; sum[i] += count[i] * j; sum[i] += count[i] * (count[i] - 1) / 2 * 10; sum[i] *= pw; if (i == 0 and j == 0) count[i]--; pw *= m; } kk2::debug::outputln(kout, count); kk2::debug::outputln(kout, sum); kk2::mint998 all_count = 1; rep (i, s.size()) all_count *= count[i]; rep (i, s.size()) { res += sum[i] * all_count / count[i]; } kout << res << kendl; } int main() { int t = 1; // kin >> t; rep (t) solve(); return 0; } // Author: kk2 // converted by https://github.com/kk2a/cpp-bundle // 2025-04-04 23:09:42