結果
| 問題 |
No.3202 Periodic Alternating Subsequence
|
| ユーザー |
 kk2a
|
| 提出日時 | 2025-07-11 23:34:25 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 664 ms / 2,000 ms |
| コード長 | 47,268 bytes |
| コンパイル時間 | 2,177 ms |
| コンパイル使用メモリ | 154,364 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-07-11 23:34:42 |
| 合計ジャッジ時間 | 16,372 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 24 |
ソースコード
#include <array>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <optional>
#include <cassert>
#include <deque>
#include <fstream>
#include <iterator>
#include <set>
#include <utility>
#include <numeric>
#include <stack>
#include <ostream>
#include <type_traits>
#include <string>
#include <map>
#include <list>
#include <unordered_set>
#include <functional>
#include <bitset>
#include <vector>
#include <cstdint>
#include <queue>
#include <istream>
#include <unordered_map>
#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
#ifndef KK2_MATH_MONOID_MAX_HPP
#define KK2_MATH_MONOID_MAX_HPP 1
#ifndef KK2_TYPE_TRAITS_IO_HPP
#define KK2_TYPE_TRAITS_IO_HPP 1
namespace kk2 {
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_IO_HPP
namespace kk2 {
namespace monoid {
template <class S, class Compare = std::less<S>> struct Max {
static constexpr bool commutative = true;
using M = Max;
S a;
bool is_unit;
Max() : a(S()), is_unit(true) {}
Max(S a_) : a(a_), is_unit(false) {}
operator S() const { return a; }
inline static M op(M l, M r) {
if (l.is_unit or r.is_unit) return l.is_unit ? r : l;
return Compare{}(l.a, r.a) ? r : l;
}
inline static M unit() { return M(); }
bool operator==(const M &rhs) const {
return is_unit == rhs.is_unit and (is_unit or a == rhs.a);
}
bool operator!=(const M &rhs) const {
return is_unit != rhs.is_unit or (!is_unit and a != rhs.a);
}
template <class OStream, is_ostream_t<OStream> * = nullptr>
friend OStream &operator<<(OStream &os, const M &x) {
if (x.is_unit) os << "-inf";
else os << x.a;
return os;
}
template <class IStream, is_istream_t<IStream> * = nullptr>
friend IStream &operator>>(IStream &is, M &x) {
is >> x.a;
x.is_unit = false;
return is;
}
};
} // namespace monoid
} // namespace kk2
#endif // MATH_MONOID_MAX_HPP
#ifndef KK2_MATH_MONOID_MIN_HPP
#define KK2_MATH_MONOID_MIN_HPP 1
namespace kk2 {
namespace monoid {
template <class S, class Compare = std::less<S>> struct Min {
static constexpr bool commutative = true;
using M = Min;
S a;
bool is_unit;
Min() : a(S()), is_unit(true) {}
Min(S a_) : a(a_), is_unit(false) {}
operator S() const { return a; }
inline static M op(M l, M r) {
if (l.is_unit or r.is_unit) return l.is_unit ? r : l;
return Compare{}(l.a, r.a) ? l : r;
}
inline static M unit() { return M(); }
bool operator==(const M &rhs) const {
return is_unit == rhs.is_unit and (is_unit or a == rhs.a);
}
bool operator!=(const M &rhs) const {
return is_unit != rhs.is_unit or (!is_unit and a != rhs.a);
}
template <class OStream, is_ostream_t<OStream> * = nullptr>
friend OStream &operator<<(OStream &os, const M &x) {
if (x.is_unit) os << "inf";
else os << x.a;
return os;
}
template <class IStream, is_istream_t<IStream> * = nullptr>
friend IStream &operator>>(IStream &is, M &x) {
is >> x.a;
x.is_unit = false;
return is;
}
};
} // namespace monoid
} // namespace kk2
#endif // KK2_MATH_MONOID_MIN_HPP
#ifndef KK2_TYPE_TRAITS_CONTAINER_TRAITS_HPP
#define KK2_TYPE_TRAITS_CONTAINER_TRAITS_HPP 1
namespace kk2 {
template <typename T> struct is_vector : std::false_type {};
template <typename T, typename Alloc> struct is_vector<std::vector<T, Alloc>> : std::true_type {};
// コンテナかどうかを判定するtraits
template <typename T> struct is_container : std::false_type {};
// 基本的なコンテナ型の特殊化
template <typename T, typename Alloc> struct is_container<std::vector<T, Alloc>> : std::true_type {
};
template <typename CharT, typename Traits, typename Alloc>
struct is_container<std::basic_string<CharT, Traits, Alloc>> : std::true_type {};
template <typename T, std::size_t N> struct is_container<std::array<T, N>> : std::true_type {};
template <typename T, typename Alloc> struct is_container<std::deque<T, Alloc>> : std::true_type {};
template <typename T, typename Alloc> struct is_container<std::list<T, Alloc>> : std::true_type {};
// SFINAEでコンテナを判定するためのヘルパー
template <typename T> using is_container_t =
typename std::enable_if_t<is_container<T>::value, std::nullptr_t>;
} // namespace kk2
#endif // KK2_TYPE_TRAITS_CONTAINER_TRAITS_HPP
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) {
if constexpr (is_vector<T>::value) {
for (auto &u : v) fill_all(u, x);
} else {
std::fill(v.begin(), v.end(), T(x));
}
}
template <class T, class U> int iota_all(std::vector<T> &v, U x, int offset = 0) {
if constexpr (is_vector<T>::value) {
for (auto &u : v) offset += iota_all(u, x + offset);
} else {
for (auto &u : v) u = x++, ++offset;
}
return offset;
}
template <class C> int mysize(const C &c) { return size(c); }
// T: commutative monoid, F: (U, T) -> U
template <class U, class T, class F>
U all_monoid_prod(const std::vector<T> &v, U unit, const F &f) {
U res = unit;
if constexpr (is_vector<T>::value) {
for (const auto &x : v) res = f(res, all_monoid_prod(x, unit, f));
} else {
for (const auto &x : v) res = f(res, x);
}
return res;
}
template <class U, class T> U all_sum(const std::vector<T> &v, U unit = U()) {
return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a + b; });
}
template <class U, class T> U all_prod(const std::vector<T> &v, U unit = U(1)) {
return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a * b; });
}
template <class U, class T> U all_xor(const std::vector<T> &v, U unit = U()) {
return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a ^ b; });
}
template <class U, class T> U all_and(const std::vector<T> &v, U unit = U(-1)) {
return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a & b; });
}
template <class U, class T> U all_or(const std::vector<T> &v, U unit = U()) {
return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a | b; });
}
template <class U, class T> U all_min(const std::vector<T> &v) {
return all_monoid_prod<monoid::Min<U>, T>(v, monoid::Min<U>::unit(), monoid::Min<U>::op);
}
template <class U, class T> U all_max(const std::vector<T> &v) {
return all_monoid_prod<monoid::Max<U>, T>(v, monoid::Max<U>::unit(), monoid::Max<U>::op);
}
template <class U, class T> U all_gcd(const std::vector<T> &v, U unit = U()) {
return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return std::gcd(a, b); });
}
template <class U, class T> U all_lcm(const std::vector<T> &v, U unit = U(1)) {
return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return std::lcm(a, b); });
}
} // namespace kk2
#endif // KK2_TEMPLATE_FUNCTION_UTIL_HPP
#ifndef KK2_TEMPLATE_IO_UTIL_HPP
#define KK2_TEMPLATE_IO_UTIL_HPP 1
// なんか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();
}
std::vector<std::string> sep(const char *s) {
std::vector<std::string> res;
std::string now;
int dep = 0;
while (true) {
if (*s == '\0') {
res.emplace_back(now);
break;
}
if (*s == '(' or *s == '[' or *s == '{') dep++;
if (*s == ')' or *s == ']' or *s == '}') dep--;
if (dep == 0 and *s == ',') {
res.emplace_back(now);
now.clear();
} else if (!isspace(*s)) {
now += *s;
}
s++;
}
return res;
}
void show_vars(const std::vector<std::string> &, int) {}
template <class T, class... Args>
void show_vars(const std::vector<std::string> &name, int pos, const T &t, const Args &...args) {
// assert(pos < (int)name.size());
output(std::cerr, name[pos++] + ":", t);
if (sizeof...(args) > 0) output(std::cerr, ", ");
show_vars(name, pos, args...);
}
#define kdebug(...) \
std::cerr << "line:" << __LINE__ << ' '; \
kk2::debug::show_vars(kk2::debug::sep(#__VA_ARGS__), 0, __VA_ARGS__); \
std::cerr << std::endl;
#define kput(s) \
std::cerr << "line:" << __LINE__ << ' '; \
kk2::debug::outputln(std::cerr, s);
#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 &...) {}
template <class... Args> void fix_warn(const Args &...) {}
#define kdebug(...) kk2::debug::fix_warn(__VA_ARGS__);
#define kput(s) kk2::debug::fix_warn(s)
#endif // KK2
} // namespace debug
} // namespace kk2
#endif // KK2_TEMPLATE_DEBUG_HPP
#ifndef KK2_MODINT_MONT_HPP
#define KK2_MODINT_MONT_HPP 1
#ifndef KK2_TYPE_TRAITS_INTERGRAL_HPP
#define KK2_TYPE_TRAITS_INTERGRAL_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>;
} // namespace kk2
#endif // KK2_TYPE_TRAITS_INTERGRAL_HPP
namespace kk2 {
template <int p> struct LazyMontgomeryModInt {
using mint = LazyMontgomeryModInt;
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
static constexpr u32 get_r() {
u32 ret = p;
for (int i = 0; i < 4; ++i) ret *= 2 - p * ret;
return ret;
}
static constexpr u32 r = get_r();
static constexpr u32 n2 = -u64(p) % p;
static_assert(r * p == 1, "invalid, r * p != 1");
static_assert(p < (1 << 30), "invalid, p >= 2 ^ 30");
static_assert((p & 1) == 1, "invalid, p % 2 == 0");
u32 _v;
constexpr LazyMontgomeryModInt() : _v(0) {}
template <typename T, is_integral_t<T> * = nullptr> constexpr LazyMontgomeryModInt(T b)
: _v(reduce(u64(b % p + p) * n2)) {}
static constexpr u32 reduce(const u64 &b) { return (b + u64(u32(b) * u32(-r)) * p) >> 32; }
constexpr mint &operator++() { return *this += 1; }
constexpr mint &operator--() { return *this -= 1; }
constexpr mint operator++(int) {
mint ret = *this;
*this += 1;
return ret;
}
constexpr mint operator--(int) {
mint ret = *this;
*this -= 1;
return ret;
}
constexpr mint &operator+=(const mint &b) {
if (i32(_v += b._v - 2 * p) < 0) _v += 2 * p;
return *this;
}
constexpr mint &operator-=(const mint &b) {
if (i32(_v -= b._v) < 0) _v += 2 * p;
return *this;
}
constexpr mint &operator*=(const mint &b) {
_v = reduce(u64(_v) * b._v);
return *this;
}
constexpr mint &operator/=(const mint &b) {
*this *= b.inv();
return *this;
}
constexpr bool operator==(const mint &b) const {
return (_v >= p ? _v - p : _v) == (b._v >= p ? b._v - p : b._v);
}
constexpr bool operator!=(const mint &b) const {
return (_v >= p ? _v - p : _v) != (b._v >= p ? b._v - p : b._v);
}
constexpr mint operator-() const { return mint() - mint(*this); }
constexpr mint operator+() const { return mint(*this); }
friend constexpr mint operator+(const mint &a, const mint &b) { return mint(a) += b; }
friend constexpr mint operator-(const mint &a, const mint &b) { return mint(a) -= b; }
friend constexpr mint operator*(const mint &a, const mint &b) { return mint(a) *= b; }
friend constexpr mint operator/(const mint &a, const mint &b) { return mint(a) /= b; }
template <class T> constexpr mint pow(T n) const {
mint ret(1), mul(*this);
while (n > 0) {
if (n & 1) ret *= mul;
if (n >>= 1) mul *= mul;
}
return ret;
}
constexpr mint inv() const {
assert(*this != mint(0));
return pow(p - 2);
}
template <class OStream, is_ostream_t<OStream> * = nullptr>
friend OStream &operator<<(OStream &os, const mint &x) {
return os << x.val();
}
template <class IStream, is_istream_t<IStream> * = nullptr>
friend IStream &operator>>(IStream &is, mint &x) {
i64 t;
is >> t;
x = mint(t);
return (is);
}
constexpr u32 val() const {
u32 ret = reduce(_v);
return ret >= p ? ret - p : ret;
}
static constexpr u32 getmod() { return p; }
};
template <int p> using Mont = LazyMontgomeryModInt<p>;
using mont998 = Mont<998244353>;
using mont107 = Mont<1000000007>;
} // namespace kk2
#endif // KK2_MODINT_MONT_HPP
#ifndef KK2_MATRIX_MATRIX_FIELD_HPP
#define KK2_MATRIX_MATRIX_FIELD_HPP 1
namespace kk2 {
/**
* @brief 行列
*
* @tparam Field invメンバが必要
*/
template <class Field> struct MatrixField {
using value_type = Field;
using mat = MatrixField;
int _h, _w;
std::vector<std::vector<Field>> _mat;
MatrixField() : MatrixField(0) {}
MatrixField(int n) : MatrixField(n, n) {}
MatrixField(int h, int w) {
if (h == 0) {
_h = 0;
_w = w;
} else {
_h = h;
_w = w;
_mat.resize(h, std::vector<Field>(w));
}
}
MatrixField(const std::vector<std::vector<Field>> &mat_)
: _h(mat_.size()),
_w(mat_[0].size()),
_mat(mat_) {}
static mat unit(int n) {
mat res(n, n);
for (int i = 0; i < n; i++) res[i][i] = Field(1);
return res;
}
inline int get_h() const { return _h; }
inline int get_w() const { return _w; }
std::vector<Field> &operator[](int i) {
assert(0 <= i && i < _h);
return _mat[i];
}
const std::vector<Field> &operator[](int i) const {
assert(0 <= i && i < _h);
return _mat[i];
}
template <class IStream, is_istream_t<IStream> * = nullptr> mat &input(IStream &is) {
for (int i = 0; i < _h; i++) {
for (int j = 0; j < _w; j++) { is >> _mat[i][j]; }
}
return *this;
}
template <class OStream, is_ostream_t<OStream> * = nullptr> void output(OStream &os) const {
for (int i = 0; i < _h; i++) {
for (int j = 0; j < _w; j++) os << _mat[i][j] << " \n"[j == _w - 1];
}
}
template <class OStream, is_ostream_t<OStream> * = nullptr>
void debug_output(OStream &os) const {
os << "(h, w): " << "(" << _h << ", " << _w << "), [\n";
for (int i = 0; i < _h; i++) {
os << " [ ";
for (int j = 0; j < _w; j++) os << _mat[i][j] << " ";
os << "]\n";
}
os << "]\n";
}
mat &operator+=(const mat &rhs) {
assert(_h == rhs._h);
assert(_w == rhs._w);
for (int i = 0; i < _h; i++) {
for (int j = 0; j < _w; j++) { _mat[i][j] += rhs._mat[i][j]; }
}
return *this;
}
mat &operator-=(const mat &rhs) {
assert(_h == rhs._h);
assert(_w == rhs._w);
for (int i = 0; i < _h; i++) {
for (int j = 0; j < _w; j++) { _mat[i][j] -= rhs._mat[i][j]; }
}
return *this;
}
mat &operator*=(const mat &rhs) {
assert(_w == rhs._h);
std::vector<std::vector<Field>> res(_h, std::vector<Field>(rhs._w, Field()));
for (int i = 0; i < _h; i++) {
for (int k = 0; k < _w; k++) {
for (int j = 0; j < rhs._w; j++) { res[i][j] += _mat[i][k] * rhs._mat[k][j]; }
}
}
_w = rhs._w;
_mat = std::move(res);
return *this;
}
/**
* @brief 掃き出し
* @tparam RREF 行簡約化行列にするかどうか
* @tparam EARLY_TERMINATE フルランクでないことが確定したときに即打ち切るかどうか
* @param wr 列が[0, wr)の範囲だけで掃き出す．指定がないなら全体で掃き出す．
* @return ランクと行列式を返す．
*/
template <bool RREF = true, bool EARLY_TERMINATE = false>
std::pair<int, Field> sweep(int wr = -1) {
if (wr == -1) wr = _w;
int r = 0;
Field det = 1;
for (int i = 0; i < wr; ++i) {
if (r >= _h) break;
int pivot = r;
while (pivot < _h and _mat[pivot][i] == Field(0)) ++pivot;
if (pivot == _h) {
if constexpr (EARLY_TERMINATE) return {-1, Field(0)};
det = 0;
continue;
}
if (r != pivot) {
det = -det;
std::swap(_mat[r], _mat[pivot]);
}
det *= _mat[r][i];
Field inv = _mat[r][i].inv();
for (int j = i; j < wr; ++j) _mat[r][j] *= inv;
for (int j = RREF ? 0 : r + 1; j < _h; ++j) {
if (j == r) continue;
Field a = _mat[j][i];
if (a == Field(0)) continue;
for (int k = i; k < wr; ++k) { _mat[j][k] -= _mat[r][k] * a; }
}
r++;
}
return {r, det};
}
mat &to_upper_Hessenberg() {
assert(_h == _w);
int n = _h;
for (int i = 0; i < n - 1; ++i) {
int pivot = i + 1;
while (pivot < n and _mat[pivot][i] == Field(0)) ++pivot;
if (pivot == n) continue;
if (pivot != i + 1) {
std::swap(_mat[pivot], _mat[i + 1]);
for (int j = 0; j < n; ++j) std::swap(_mat[j][i + 1], _mat[j][pivot]);
}
if (_mat[i + 1][i] != Field(1)) {
Field a = _mat[i + 1][i], iv = a.inv();
for (int j = i; j < n; ++j) _mat[i + 1][j] *= iv;
for (int j = 0; j < n; ++j) _mat[j][i + 1] *= a;
}
for (int j = i + 2; j < n; ++j) {
Field a = _mat[j][i];
if (a == Field(0)) continue;
for (int k = i; k < n; ++k) _mat[j][k] -= _mat[i + 1][k] * a;
for (int k = 0; k < n; ++k) _mat[k][i + 1] += _mat[k][j] * a;
}
}
return *this;
}
Field det() const {
assert(_h == _w);
return mat(*this).sweep<false, true>().second;
}
std::optional<mat> inv() const {
assert(_h == _w);
int n = _h;
mat res(*this);
res.inplace_combine_right(mat::unit(n));
int r = res.sweep<true, true>().first;
if (r != n) return std::nullopt;
for (int i = 0; i < n; i++) res._mat[i].erase(res[i].begin(), res[i].begin() + n);
res._w = n;
return res;
}
int rank() const { return mat(*this).sweep<false, false>().first; }
mat &shrink() {
while (_h and _mat.back() == std::vector<Field>(_w, Field())) _mat.pop_back(), _h--;
return *this;
}
template <class T> mat pow(T n) const {
assert(_h == _w);
assert(n >= 0);
mat mul(_mat), res = mat::unit(_h);
while (n) {
if (n & 1) res *= mul;
if (n >>= 1) mul *= mul;
}
return res;
}
std::optional<mat> solve(const mat &b) const {
assert(_h == b._h);
assert(b._w == 1);
mat ab = combine_right(b);
int r = ab.sweep<true, false>().first;
if ([&]() {
if (!r) return false;
for (int i = 0; i < _w; i++)
if (ab[r - 1][i] != Field()) return false;
return true;
}()) {
return std::nullopt;
}
mat res(1 + _w - r, _w);
std::vector<int> idx(_w, -1), step(r, -1);
for (int i = 0, j = 0, now = 0; j < _w; j++) {
if (i == r or ab[i][j] == Field(0)) idx[j] = now, res[1 + now++][j] = 1;
else res[0][j] = ab[i].back(), step[i++] = j;
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < _w; j++) {
if (idx[j] != -1) res[idx[j] + 1][step[i]] = -ab[i][j];
}
}
return res;
}
mat &inplace_combine_top(const mat &rhs) {
assert(_w == rhs._w);
_mat.insert(_mat.begin(), rhs._mat.begin(), rhs._mat.end());
_h += rhs._h;
return *this;
}
mat &inplace_combine_bottom(const mat &rhs) {
assert(_w == rhs._w);
_mat.insert(_mat.end(), rhs._mat.begin(), rhs._mat.end());
_h += rhs._h;
return *this;
}
mat &inplace_combine_left(const mat &rhs) {
assert(_h == rhs._h);
for (int i = 0; i < _h; i++) _mat[i].insert(_mat[i].begin(), rhs[i].begin(), rhs[i].end());
_w += rhs._w;
return *this;
}
mat &inplace_combine_right(const mat &rhs) {
assert(_h == rhs._h);
for (int i = 0; i < _h; i++) _mat[i].insert(_mat[i].end(), rhs[i].begin(), rhs[i].end());
_w += rhs._w;
return *this;
}
mat transpose() const {
mat res(_w, _h);
for (int i = 0; i < _h; i++) {
for (int j = 0; j < _w; j++) { res[j][i] = _mat[i][j]; }
}
return res;
}
mat combine_top(const mat &rhs) const { return mat(*this).inplace_combine_top(rhs); }
mat combine_bottom(const mat &rhs) const { return mat(*this).inplace_combine_bottom(rhs); }
mat combine_left(const mat &rhs) const { return mat(*this).inplace_combine_left(rhs); }
mat combine_right(const mat &rhs) const { return mat(*this).inplace_combine_right(rhs); }
mat &inplace_transpose() { return *this = transpose(); }
friend mat operator+(const mat &lhs, const mat &rhs) { return mat(lhs) += rhs; }
friend mat operator-(const mat &lhs, const mat &rhs) { return mat(lhs) -= rhs; }
friend mat operator*(const mat &lhs, const mat &rhs) { return mat(lhs) *= rhs; }
friend bool operator==(const mat &lhs, const mat &rhs) { return lhs._mat == rhs._mat; }
friend bool operator!=(const mat &lhs, const mat &rhs) { return lhs._mat != rhs._mat; }
};
} // namespace kk2
#endif // KK2_MATRIX_MATRIX_FIELD_HPP
// #include <kk2/fps/fps_arb.hpp>
using namespace std;
void solve() {
/*
1, 0, 1, 0, ...
0, 1, 0, 1, ...
の長さの二乗の和
外から0で始まっていると考えるてきな
2, 1, 0乗和を持てば更新可能
dp[i][j][k] = i文字目まで，j乗和の和，最後k
result:
dp[|T|K][2][0] + dp[|T|K][2][1]
s[i] = 0
dp[i][2][0] = dp[i-1][2][0] + dp[i-1][2][1] + 2 * dp[i-1][1][1] + dp[i-1][0][1] + 1
dp[i][1][0] = dp[i-1][1][0] + dp[i-1][1][1] + dp[i-1][0][1] + 1
dp[i][0][0] = dp[i-1][0][0] + dp[i-1][0][1] + 1
dp[i][*][1] = dp[i-1][*][1]
s[i] = 1
onaji
|T|ごとに進むときは，アフィン変換になる
*/
using mint = kk2::mont107;
using mat = kk2::MatrixField<mint>;
// using fps = kk2::FPSArb<mint>;
string t;
kin >> t;
i64 k;
kin >> k;
mat A(6, 6), b(6, 1);
A = mat::unit(6);
rep (i, t.size()) {
mat nA(6, 6), nb(6, 1);
nA = mat::unit(6);
if (t[i] == '0') {
nA[4][5] = 1;
nA[4][3] = 2;
nA[4][1] = 1;
nA[2][3] = 1;
nA[2][1] = 1;
nA[0][1] = 1;
nb[4][0] = 1;
nb[2][0] = 1;
nb[0][0] = 1;
} else {
nA[5][4] = 1;
nA[5][2] = 2;
nA[5][0] = 1;
nA[3][2] = 1;
nA[3][0] = 1;
nA[1][0] = 1;
nb[5][0] = 1;
nb[3][0] = 1;
nb[1][0] = 1;
}
A = nA * A, b = nA * b + nb;
kdebug(b);
}
kdebug(A);
auto pow_sum = [](auto self, const mat& A, i64 l) {
// A^{l-1} + ... + A^0
if (l == 1) return mat::unit(A.get_h());
mat tmp = (A.pow(l / 2) + mat::unit(A.get_h())) * self(self, A, l / 2);
if (l & 1) tmp = A * tmp + mat::unit(A.get_h());
return tmp;
};
// mat s = vvc<mint>{{1, 1}, {0, 1}};
// kdebug(pow_sum(pow_sum, s, 1));
// kdebug(pow_sum(pow_sum, s, 2));
// kdebug(pow_sum(pow_sum, s, 3));
// kdebug(pow_sum(pow_sum, s, 4));
auto res = pow_sum(pow_sum, A, k) * b;
kdebug(res);
kout << res[4][0] + res[5][0] << "\n";
}
int main() {
#ifdef KK2
int t = 2;
#else
int t = 1;
#endif
// kin >> t;
rep (t) solve();
return 0;
}
// Author: kk2
// converted by https://github.com/kk2a/cpp-bundle
// 2025-07-11 23:34:20