Submission #691654
Source Code Expand
//ここからテンプレート
#if 1
#include<iostream>
#include<list>
#include<algorithm>
#include<utility>
#include<type_traits>
#include<tuple>
#include<memory>
#include<iterator>
#include<string>
#include<functional>
#include<list>
#include<array>
#include<complex>
#include<numeric>
#include<iomanip>
#include<vector>
#include<queue>
#include<random>
#include<boost/optional.hpp>
#include<boost/optional/optional_io.hpp>
#include<boost/variant.hpp>
#include<boost/range/adaptor/transformed.hpp>
#include<boost/range/adaptor/indexed.hpp>
#include<boost/range/adaptor/filtered.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/irange.hpp>
#include<boost/multi_array.hpp>
typedef long long int int64;
typedef unsigned long long uint64;
typedef long double double64;
constexpr int int_max_value = 0x7FFFFFFF;
constexpr unsigned int uint_max_value = 0xFFFFFFFF;
constexpr int64 int64_max_value = 0x7FFFFFFFFFFFFFFF;
constexpr uint64 uint64_max_value = 0xFFFFFFFFFFFFFFFF;
namespace utility
{
namespace detail
{
template<class>struct apply_tuple_t;
template<std::size_t... Is>struct apply_tuple_t<std::index_sequence<Is...>>
{
template<class Func, class Tuple>static decltype(auto) run(Func func, Tuple const& t)
{
return func(std::get<Is>(t)...);
}
};
}
template<class Func, class... Args>decltype(auto) apply_tuple(Func func, std::tuple<Args...>const& vec)
{
return detail::apply_tuple_t<std::make_index_sequence<sizeof...(Args)>>::run(func, vec);
}
template<class T, std::size_t I>constexpr T const& front(T const(&ar)[I])
{
return ar[0];
}
template<class Range>auto front(Range const& vec)->decltype(vec[0]) const&
{
return vec[0];
}
template<class Range>auto front(Range const& vec)->typename std::enable_if<
!std::is_same<typename std::iterator_traits<decltype(vec.begin())>::iterator_category,std::random_access_iterator_tag>::value,
decltype(vec.front()) const&>::type
{
return vec.front();
}
template<class T, std::size_t I>constexpr T const& back(T const(&ar)[I])
{
return ar[I - 1];
}
template<class Range>auto back(Range const& vec)->decltype(vec[0]) const&
{
return vec[vec.size() - 1];
}
template<class Range>auto back(Range const& vec)->typename std::enable_if<
!std::is_same<typename std::iterator_traits<decltype(vec.begin())>::iterator_category, std::random_access_iterator_tag>::value,
decltype(vec.front()) const&>::type
{
return vec.back();
}
template<class T>using point = std::pair<T, T>;
template<class Func>struct scope_exit_t
{
Func func;
scope_exit_t(Func f) :func(f) {}
scope_exit_t(scope_exit_t &&) = delete;
scope_exit_t(scope_exit_t const&) = delete;
scope_exit_t& operator=(scope_exit_t &&) = delete;
scope_exit_t& operator=(scope_exit_t const&) = delete;
~scope_exit_t()
{
func();
}
};
template<class Func>scope_exit_t<Func> scope_exit(Func func)
{
return scope_exit_t<Func>(func);
}
namespace detail
{
template<class Func, class T, class U>auto fold_expression_i(Func func, T const& v, U const& u)
{
return func(v, u);
}
template<class Func, class T, class... Ts>auto fold_expression_i(Func func, T const& v, Ts const&... vs)
{
return func(v, fold_expression_i(func, vs...));
}
template<class Func, class T, std::size_t... Is>auto fold_expression(Func func, T const& v, std::index_sequence<Is...>)
{
return fold_expression_i(func, std::get<Is>(v)...);
}
}
template<class Func, class... Ts>auto fold_expression(std::tuple<Ts...>const& tup, Func func)
{
return detail::fold_expression(func, tup, std::make_index_sequence<sizeof...(Ts)>());
}
template<class... Ts>auto tuple_add(std::tuple<Ts...>const& tup)
{
return fold_expression(tup, [](auto lhs, auto rhs) {return lhs + rhs;});
}
template<class... Ts>auto tuple_mul(std::tuple<Ts...>const& tup)
{
return fold_expression(tup, [](auto lhs, auto rhs) {return lhs * rhs;});
}
}
namespace container
{
template<class Type, std::size_t Max>class value_tank
{
std::array<boost::optional<Type>, Max> value_ = {};
std::size_t size_ = 0;
public:
value_tank() = default;
value_tank(value_tank const&) = default;
value_tank(value_tank&&) = default;
value_tank& operator=(value_tank const&) = default;
value_tank& operator=(value_tank&&) = default;
~value_tank() = default;
std::size_t size()const
{
return size_;
}
struct iterator :std::iterator<std::input_iterator_tag, Type>
{
boost::optional<Type> const* ptr_;
iterator(boost::optional<Type> const*ptr) :ptr_(ptr){}
iterator(iterator const&) = default;
iterator(iterator&&) = default;
iterator& operator=(iterator const&) = default;
iterator& operator=(iterator&&) = default;
~iterator() = default;
Type const& operator*()const
{
return **ptr_;
}
iterator& operator++()
{
++ptr_;
return *this;
}
iterator operator++(int)
{
auto ret = *this;
++ptr_;
return ret;
}
bool operator==(iterator const& lhs)const
{
return ptr_ == lhs.ptr_;
}
bool operator!=(iterator const& lhs)const
{
return ptr_ != lhs.ptr_;
}
};
iterator begin()const
{
return iterator(&value_[0]);
}
iterator end()const
{
return iterator(&value_[size_]);
}
void push_back(Type&& v)
{
if (size_ < Max)
{
value_[size_] = std::move(v);
++size_;
}
}
void push_back(Type const& v)
{
if (size_ < Max)
{
value_[size_] = v;
++size_;
}
}
Type const& operator[](std::size_t index)const
{
return *(value_[index]);
}
};
}
namespace adaptor
{
using namespace boost::adaptors;
}
namespace algorithm
{
using namespace boost::range;
template<class SinglePassRange, class Pred>bool any_of(SinglePassRange const& range, Pred pred)
{
return std::any_of(std::begin(range), std::end(range), pred);
}
template<class SinglePassRange, class Pred>bool all_of(SinglePassRange const& range, Pred pred)
{
return std::all_of(std::begin(range), std::end(range), pred);
}
}
namespace math
{
template<class T>constexpr T pow(T p, int64 n)
{
return n == 0 ? T(1) : n == 1 ? p : n == 2 ? p*p : n % 2 == 0 ? pow(pow(p, n / 2), 2) : pow(pow(p, n / 2), 2)*p;
}
int log(long long int p, int n)
{
int64 t = n;
for (int i = 0;;++i)
{
if (t > p)
return i;
t *= n;
}
}
constexpr double pi = 3.141592653589793;
namespace detail
{
int gcd(int larger, int less)
{
return less == 0 ? larger : gcd(less, larger%less);
}
}
int gcd(int lhs, int rhs)
{
return lhs < rhs ? detail::gcd(rhs, lhs) : detail::gcd(lhs, rhs);
}
void fourier_transform(
std::vector<std::complex<double>>& vec, std::size_t N)
{
std::vector<std::complex<double>> butterfly;
vec.resize(N);
butterfly.resize(N);
std::complex<double> half(std::cos(pi), std::sin(pi));
for (uint64 i = 1, k = N / 2;i < N;[&]() {i *= 2;k /= 2;}())//i*k == N/4
{
std::complex<double> circle(std::cos(pi / i), std::sin(pi / i));
std::complex<double> c(1.0, 0);
for (auto count : boost::irange(0ull, i))
{
for (auto j : boost::irange(0ull, k))
{
butterfly[count*k + j] =
vec[2 * count*k + j] + vec[2 * count*k + j + k] * c;
butterfly[count*k + j + N / 2] =
vec[2 * count*k + j] + vec[2 * count*k + j + k] * c*half;
}
c *= circle;
}
std::swap(vec, butterfly);
}
}
class polynomial
{
std::vector<std::complex<double>> value;
void swap(polynomial&& p)
{
std::swap(value, p.value);
}
public:
polynomial() :value{ 0.0 } {}
polynomial(polynomial const&) = default;
polynomial(std::vector<std::complex<double>>&& vec) :value(std::move(vec)) {}
polynomial(polynomial&& p) :polynomial()
{
swap(std::move(p));
}
polynomial(std::initializer_list<std::complex<double>> lis) :value(lis) {}
polynomial(std::complex<double> c) :polynomial({ c }) {}
polynomial& operator=(polynomial const&) = default;
polynomial& operator=(polynomial&& p)
{
value = std::vector<std::complex<double>>{ 0.0 };
swap(std::move(p));
return *this;
}
~polynomial() = default;
std::complex<double> operator[](std::size_t deg)const
{
return deg >= value.size() ? 0.0 : value[deg];
}
std::size_t degree()const
{
return value.size() - 1;
}
void strict_degree_set()
{
std::size_t N = degree();
for (;N > 0;--N)
{
if (value[N] != 0.0)
break;
}
value.resize(N + 1);
}
void integer_degree_set()
{
std::size_t N = degree();
for (;N > 0;--N)
{
std::cout << value[N] << " " << (std::norm(value[N]) > (1.0e-20)) << std::endl;
if (std::norm(value[N]) > (1.0e-20))
break;
}
value.resize(N + 1);
}
friend polynomial operator*(polynomial const& lhs, polynomial const& rhs)
{
std::size_t N = 1;
while (true)
{
N *= 2;
if (N > (lhs.degree() + rhs.degree()))
break;
}
auto lhs_ = lhs.value;
auto rhs_ = rhs.value;
fourier_transform(lhs_, N);
fourier_transform(rhs_, N);
std::vector<std::complex<double>> vec;
vec.reserve(N);
for (std::size_t i = 0;i < N;++i)
{
vec.push_back(lhs_[i] * rhs_[i]);
}
for (auto& v : vec)
{
v = 2 * v.real() - v;
}
fourier_transform(vec, N);
for (auto& v : vec)
{
v = (2 * v.real() - v)*(1.0 / N);
}
std::size_t k = N;
for (;k > 0;--k)
{
if (std::norm(vec[k]) > 1.0e-23)
break;
}
vec.resize(k + 1);
return polynomial(std::move(vec));
}
};
int real_integer(std::complex<double> c)
{
int v = static_cast<int>(c.real());
double u = c.real() - v;
return v + static_cast<int>(2 * u);
}
template<class T>polynomial make_poly(std::vector<T> const& vec)
{
auto range = vec | adaptor::transformed([](T const& v) {return static_cast<std::complex<double>>(v);});
std::vector<std::complex<double>> ret(std::begin(range), std::end(range));
return polynomial(std::move(ret));
}
polynomial make_poly(std::initializer_list<double>init)
{
std::vector<std::complex<double>> vec;
for (auto v : init)
{
vec.emplace_back(v);
}
return polynomial(std::move(vec));
}
polynomial make_poly(std::initializer_list<int> init)
{
std::vector<std::complex<double>> vec;
for (auto v : init)
{
vec.emplace_back(v);
}
return polynomial(std::move(vec));
}
template<class T>class infinite_value
{
boost::optional<T> val;
public:
infinite_value(T const& v) :val(v) {}
infinite_value(T&& v) :val(std::move(v)) {}
infinite_value(boost::none_t = boost::none) :val() {}
infinite_value(infinite_value const&) = default;
infinite_value(infinite_value&&) = default;
~infinite_value() = default;
infinite_value& operator=(T const& v)
{
val = v;
return *this;
}
infinite_value& operator=(T&& v)
{
val = std::move(v);
return *this;
}
infinite_value& operator=(boost::none_t)
{
val = boost::none;
return *this;
}
infinite_value& operator=(infinite_value const&) = default;
infinite_value& operator=(infinite_value&&) = default;
operator bool()const
{
return static_cast<bool>(val);
}
T const& operator*()const
{
return *val;
}
friend infinite_value operator+(infinite_value const& lhs, infinite_value const& rhs)
{
return lhs&&rhs ? infinite_value<T>(*lhs + *rhs) : infinite_value<T>(boost::none);
}
friend infinite_value operator+(infinite_value const& lhs, T const& rhs)
{
return lhs ? infinite_value<T>(*lhs + rhs) : infinite_value<T>(boost::none);
}
friend infinite_value operator+(T const& lhs, infinite_value const& rhs)
{
return lhs&&rhs ? infinite_value<T>(*lhs + *rhs) : infinite_value<T>(boost::none);
}
friend bool operator==(infinite_value const& lhs, infinite_value const& rhs)
{
return (!lhs&&!rhs) || (lhs&&rhs && (*lhs == *rhs));
}
friend bool operator==(infinite_value const& lhs, T const& rhs)
{
return lhs && (*lhs == rhs);
}
friend bool operator==(T const& lhs, infinite_value const& rhs)
{
return rhs && (lhs == *rhs);
}
friend bool operator<(infinite_value const& lhs, infinite_value const& rhs)
{
return !lhs ? false : !rhs ? true : *lhs < *rhs;
}
friend bool operator<(infinite_value const& lhs, T const& rhs)
{
return !lhs ? false : *lhs < rhs;
}
friend bool operator<(T const& lhs, infinite_value const& rhs)
{
return !rhs ? true : lhs < *rhs;
}
friend bool operator<=(infinite_value const& lhs, infinite_value const& rhs)
{
return (lhs < rhs) || (lhs == rhs);
}
friend bool operator<=(infinite_value const& lhs, T const& rhs)
{
return (lhs < rhs) || (lhs == rhs);
}
friend bool operator<=(T const& lhs, infinite_value const& rhs)
{
return (lhs < rhs) || (lhs == rhs);
}
friend bool operator>(infinite_value const& lhs, infinite_value const& rhs)
{
return !rhs ? false : !lhs ? true : *lhs > *rhs;
}
friend bool operator>(infinite_value const& lhs, T const& rhs)
{
return !lhs ? true : *lhs > rhs;
}
friend bool operator>(T const& lhs, infinite_value const& rhs)
{
return !rhs ? false : lhs > *rhs;
}
friend bool operator>=(infinite_value const& lhs, infinite_value const& rhs)
{
return (lhs > rhs) || (lhs == rhs);
}
friend bool operator>=(infinite_value const& lhs, T const& rhs)
{
return (lhs > rhs) || (lhs == rhs);
}
friend bool operator>=(T const& lhs, infinite_value const& rhs)
{
return (lhs > rhs) || (lhs == rhs);
}
};
template<std::size_t Mod>class modulo_number
{
uint64 val = {};
static constexpr uint64 abs(int64 n)
{
return n <= -1 ? n + Mod : n;
}
public:
modulo_number(modulo_number const&) = default;
modulo_number(modulo_number&&) = default;
modulo_number& operator=(modulo_number const&) = default;
modulo_number& operator=(modulo_number&&) = default;
~modulo_number() = default;
constexpr modulo_number(uint64 num = {}) : val(num%Mod) {}
constexpr modulo_number(unsigned int num) : val(num%Mod) {}
constexpr modulo_number(int64 num) : val(abs(num%Mod)) {}
constexpr modulo_number(int num) : val(abs(num%Mod)) {}
modulo_number& operator=(uint64 num)
{
val = num%Mod;
return *this;
}
modulo_number& operator=(int64 num)
{
val = abs(num%Mod);
return *this;
}
modulo_number& operator=(unsigned int num)
{
val = num%Mod;
return *this;
}
modulo_number& operator=(int num)
{
val = abs(num%Mod);
return *this;
}
constexpr uint64 get()const
{
return val;
}
friend constexpr modulo_number<Mod> operator+(modulo_number<Mod>const& lhs, modulo_number<Mod>const& rhs)
{
return modulo_number<Mod>((lhs.val + rhs.val) % Mod);
}
friend constexpr modulo_number<Mod> operator+(modulo_number<Mod>const& lhs, int const& rhs)
{
return lhs + modulo_number<Mod>(rhs);
}
friend constexpr modulo_number<Mod> operator+(modulo_number<Mod>const& lhs, unsigned int const& rhs)
{
return lhs + modulo_number<Mod>(rhs);
}
friend constexpr modulo_number<Mod> operator+(modulo_number<Mod>const& lhs, int64 const& rhs)
{
return lhs + modulo_number<Mod>(rhs);
}
friend constexpr modulo_number<Mod> operator+(modulo_number<Mod>const& lhs, uint64 const& rhs)
{
return lhs + modulo_number<Mod>(rhs);
}
friend constexpr modulo_number<Mod> operator+(int const& lhs, modulo_number<Mod>const& rhs)
{
return modulo_number<Mod>(lhs) + rhs;
}
friend constexpr modulo_number<Mod> operator+(unsigned int const& lhs, modulo_number<Mod>const& rhs)
{
return modulo_number<Mod>(lhs) + rhs;
}
friend constexpr modulo_number<Mod> operator+(int64 const& lhs, modulo_number<Mod>const& rhs)
{
return modulo_number<Mod>(lhs) + rhs;
}
friend constexpr modulo_number<Mod> operator+(uint64 const& lhs, modulo_number<Mod>const& rhs)
{
return modulo_number<Mod>(lhs) + rhs;
}
friend constexpr modulo_number<Mod> operator-(modulo_number<Mod>const& lhs, modulo_number<Mod>const& rhs)
{
return modulo_number<Mod>((lhs.val + Mod - rhs.val) % Mod);
}
friend constexpr modulo_number<Mod> operator-(modulo_number<Mod>const& lhs, int const& rhs)
{
return lhs - modulo_number<Mod>(rhs);
}
friend constexpr modulo_number<Mod> operator-(modulo_number<Mod>const& lhs, unsigned int const& rhs)
{
return lhs - modulo_number<Mod>(rhs);
}
friend constexpr modulo_number<Mod> operator-(modulo_number<Mod>const& lhs, int64 const& rhs)
{
return lhs - modulo_number<Mod>(rhs);
}
friend constexpr modulo_number<Mod> operator-(modulo_number<Mod>const& lhs, uint64 const& rhs)
{
return lhs - modulo_number<Mod>(rhs);
}
friend constexpr modulo_number<Mod> operator-(int const& lhs, modulo_number<Mod>const& rhs)
{
return modulo_number<Mod>(lhs) - rhs;
}
friend constexpr modulo_number<Mod> operator-(unsigned int const& lhs, modulo_number<Mod>const& rhs)
{
return modulo_number<Mod>(lhs) - rhs;
}
friend constexpr modulo_number<Mod> operator-(int64 const& lhs, modulo_number<Mod>const& rhs)
{
return modulo_number<Mod>(lhs) - rhs;
}
friend constexpr modulo_number<Mod> operator-(uint64 const& lhs, modulo_number<Mod>const& rhs)
{
return modulo_number<Mod>(lhs) - rhs;
}
friend constexpr modulo_number<Mod> operator*(modulo_number<Mod>const& lhs, modulo_number<Mod>const& rhs)
{
return modulo_number<Mod>((lhs.val*rhs.val) % Mod);
}
friend constexpr modulo_number<Mod> operator*(modulo_number<Mod>const& lhs, int const& rhs)
{
return lhs * modulo_number<Mod>(rhs);
}
friend constexpr modulo_number<Mod> operator*(modulo_number<Mod>const& lhs, unsigned int const& rhs)
{
return lhs * modulo_number<Mod>(rhs);
}
friend constexpr modulo_number<Mod> operator*(modulo_number<Mod>const& lhs, int64 const& rhs)
{
return lhs * modulo_number<Mod>(rhs);
}
friend constexpr modulo_number<Mod> operator*(modulo_number<Mod>const& lhs, uint64 const& rhs)
{
return lhs * modulo_number<Mod>(rhs);
}
friend constexpr modulo_number<Mod> operator*(int const& lhs, modulo_number<Mod>const& rhs)
{
return modulo_number<Mod>(lhs) * rhs;
}
friend constexpr modulo_number<Mod> operator*(unsigned int const& lhs, modulo_number<Mod>const& rhs)
{
return modulo_number<Mod>(lhs) * rhs;
}
friend constexpr modulo_number<Mod> operator*(int64 const& lhs, modulo_number<Mod>const& rhs)
{
return modulo_number<Mod>(lhs) * rhs;
}
friend constexpr modulo_number<Mod> operator*(uint64 const& lhs, modulo_number<Mod>const& rhs)
{
return modulo_number<Mod>(lhs) * rhs;
}
friend constexpr modulo_number<Mod> operator/(modulo_number<Mod>const& lhs, modulo_number<Mod>const& rhs)
{
return lhs*math::pow(rhs, Mod - 1);
}
friend constexpr modulo_number<Mod> operator/(modulo_number<Mod>const& lhs, int const& rhs)
{
return lhs / modulo_number<Mod>(rhs);
}
friend constexpr modulo_number<Mod> operator/(modulo_number<Mod>const& lhs, unsigned int const& rhs)
{
return lhs / modulo_number<Mod>(rhs);
}
friend constexpr modulo_number<Mod> operator/(modulo_number<Mod>const& lhs, int64 const& rhs)
{
return lhs / modulo_number<Mod>(rhs);
}
friend constexpr modulo_number<Mod> operator/(modulo_number<Mod>const& lhs, uint64 const& rhs)
{
return lhs / modulo_number<Mod>(rhs);
}
friend constexpr modulo_number<Mod> operator/(int const& lhs, modulo_number<Mod>const& rhs)
{
return modulo_number<Mod>(lhs) / rhs;
}
friend constexpr modulo_number<Mod> operator/(unsigned int const& lhs, modulo_number<Mod>const& rhs)
{
return modulo_number<Mod>(lhs) / rhs;
}
friend constexpr modulo_number<Mod> operator/(int64 const& lhs, modulo_number<Mod>const& rhs)
{
return modulo_number<Mod>(lhs) / rhs;
}
friend constexpr modulo_number<Mod> operator/(uint64 const& lhs, modulo_number<Mod>const& rhs)
{
return modulo_number<Mod>(lhs) / rhs;
}
template<class Rhs>decltype(auto) operator+=(Rhs const& rhs)
{
return *this = *this + rhs;
}
template<class Rhs>decltype(auto) operator*=(Rhs const& rhs)
{
return *this = *this * rhs;
}
template<class Rhs>decltype(auto) operator-=(Rhs const& rhs)
{
return *this = *this - rhs;
}
template<class Rhs>decltype(auto) operator/=(Rhs const& rhs)
{
return *this = *this / rhs;
}
};
template<class T>constexpr T factorial(std::size_t n, std::size_t goal = 1)
{
return n == goal ? T(n) : n == 0 ? T(1) : factorial<T>(n, (n + goal) / 2 + 1)*factorial<T>((n + goal) / 2, goal);
}
namespace detail
{
constexpr uint64 integral_sqrt_i(uint64 v, uint64 start, uint64 end)
{
return start == end ? start :
pow((start + end) / 2 + 1, 2) <= v ?
integral_sqrt_i(v, (start + end) / 2 + 1, end) :
integral_sqrt_i(v, start, (start + end) / 2);
}
}
constexpr uint64 integral_sqrt(uint64 v)
{
return v == 0 ? 0 :
v == 1 ? 1 :
detail::integral_sqrt_i(v, 1, 0b100000000000000000000000000000000ull);
}
namespace detail
{
constexpr bool is_prime_i(uint64 v, uint64 start, uint64 end)
{
return start == end ? v%end != 0 :
is_prime_i(v, start, (start + end) / 2) &&
is_prime_i(v, (start + end) / 2 + 1, end);
}
}
constexpr bool is_prime(uint64 v)
{
return v == 0 ? false :
v == 1 ? false :
v == 2 ? true :
v == 3 ? true : detail::is_prime_i(v, 2, integral_sqrt(v));
}
class dynamic_modulo
{
uint64 value;
uint64 mod;
static constexpr uint64 abs(int64 v, uint64 mod)
{
return v <= -1 ? v + mod : v;
}
public:
constexpr dynamic_modulo() :value(), mod(2) {}
constexpr dynamic_modulo(uint64 v, uint64 m) : value(v), mod(m) {}
dynamic_modulo(dynamic_modulo const&) = default;
dynamic_modulo(dynamic_modulo&&) = default;
dynamic_modulo& operator=(dynamic_modulo const&) = default;
dynamic_modulo& operator=(dynamic_modulo&&) = default;
~dynamic_modulo() = default;
constexpr uint64 operator*()const
{
return value;
}
constexpr friend auto operator+(dynamic_modulo const& lhs, dynamic_modulo const& rhs)
{
return lhs.mod != rhs.mod ?
throw std::logic_error("math::dynamic_modulo mod number error") :
dynamic_modulo((lhs.value + rhs.value) % lhs.mod, lhs.mod);
}
constexpr friend auto operator+(dynamic_modulo const& lhs, uint64 const& rhs)
{
return dynamic_modulo((lhs.value + rhs) % lhs.mod, lhs.mod);
}
constexpr friend auto operator+(dynamic_modulo const& lhs, int64 const& rhs)
{
return dynamic_modulo(abs((lhs.value + rhs) % lhs.mod, lhs.mod), lhs.mod);
}
constexpr friend auto operator+(dynamic_modulo const& lhs, unsigned int const& rhs)
{
return dynamic_modulo((lhs.value + rhs) % lhs.mod, lhs.mod);
}
constexpr friend auto operator+(dynamic_modulo const& lhs, int const& rhs)
{
return dynamic_modulo(abs((lhs.value + rhs) % lhs.mod, lhs.mod), lhs.mod);
}
constexpr friend auto operator+(uint64 const& rhs, dynamic_modulo const& lhs)
{
return dynamic_modulo((lhs.value + rhs) % lhs.mod, lhs.mod);
}
constexpr friend auto operator+(int64 const& rhs, dynamic_modulo const& lhs)
{
return dynamic_modulo(abs((lhs.value + rhs) % lhs.mod, lhs.mod), lhs.mod);
}
constexpr friend auto operator+(unsigned int const& rhs, dynamic_modulo const& lhs)
{
return dynamic_modulo((lhs.value + rhs) % lhs.mod, lhs.mod);
}
constexpr friend auto operator+(int const& rhs, dynamic_modulo const& lhs)
{
return dynamic_modulo(abs((lhs.value + rhs) % lhs.mod, lhs.mod), lhs.mod);
}
constexpr friend auto operator*(dynamic_modulo const& lhs, dynamic_modulo const& rhs)
{
return lhs.mod != rhs.mod ?
throw std::logic_error("math::dynamic_modulo mod number error") :
dynamic_modulo((lhs.value * rhs.value) % lhs.mod, lhs.mod);
}
constexpr friend auto operator*(dynamic_modulo const& lhs, uint64 const& rhs)
{
return dynamic_modulo((lhs.value * rhs) % lhs.mod, lhs.mod);
}
constexpr friend auto operator*(dynamic_modulo const& lhs, int64 const& rhs)
{
return dynamic_modulo(abs((lhs.value * rhs) % lhs.mod, lhs.mod), lhs.mod);
}
constexpr friend auto operator*(dynamic_modulo const& lhs, unsigned int const& rhs)
{
return dynamic_modulo((lhs.value * rhs) % lhs.mod, lhs.mod);
}
constexpr friend auto operator*(dynamic_modulo const& lhs, int const& rhs)
{
return dynamic_modulo(abs((lhs.value * rhs) % lhs.mod, lhs.mod), lhs.mod);
}
constexpr friend auto operator*(uint64 const& rhs, dynamic_modulo const& lhs)
{
return dynamic_modulo((lhs.value * rhs) % lhs.mod, lhs.mod);
}
constexpr friend auto operator*(int64 const& rhs, dynamic_modulo const& lhs)
{
return dynamic_modulo(abs((lhs.value * rhs) % lhs.mod, lhs.mod), lhs.mod);
}
constexpr friend auto operator*(unsigned int const& rhs, dynamic_modulo const& lhs)
{
return dynamic_modulo((lhs.value * rhs) % lhs.mod, lhs.mod);
}
constexpr friend auto operator*(int const& rhs, dynamic_modulo const& lhs)
{
return dynamic_modulo(abs((lhs.value * rhs) % lhs.mod, lhs.mod), lhs.mod);
}
constexpr friend auto operator-(dynamic_modulo const& lhs, dynamic_modulo const& rhs)
{
return lhs.mod != rhs.mod ?
throw std::logic_error("math::dynamic_modulo mod number error") :
dynamic_modulo(abs((lhs.value - rhs.value) % lhs.mod, lhs.mod), lhs.mod);
}
constexpr friend auto operator-(dynamic_modulo const& lhs, uint64 const& rhs)
{
return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
}
constexpr friend auto operator-(dynamic_modulo const& lhs, int64 const& rhs)
{
return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
}
constexpr friend auto operator-(dynamic_modulo const& lhs, unsigned int const& rhs)
{
return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
}
constexpr friend auto operator-(dynamic_modulo const& lhs, int const& rhs)
{
return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
}
constexpr friend auto operator-(uint64 const& rhs, dynamic_modulo const& lhs)
{
return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
}
constexpr friend auto operator-(int64 const& rhs, dynamic_modulo const& lhs)
{
return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
}
constexpr friend auto operator-(unsigned int const& rhs, dynamic_modulo const& lhs)
{
return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
}
constexpr friend auto operator-(int const& rhs, dynamic_modulo const& lhs)
{
return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
}
};
}
namespace string
{
namespace detail
{
struct substring
{
std::string const& str_;
std::size_t start_;
std::size_t size_;
bool operator==(substring const& rhs)const
{
if (size_ != rhs.size_)
return false;
for (std::size_t i = 0;i < size_;++i)
{
if (rhs.str_[rhs.start_ + i] != str_[start_ + i])
return false;
}
return true;
}
bool operator!=(substring const& rhs)const
{
return !(rhs.operator==(*this));
}
std::string str()const
{
return str_.substr(start_, size_);
}
};
struct substring_iterator :std::iterator<std::input_iterator_tag, substring>
{
std::string const& str_;
std::size_t start_;
std::size_t size_;
substring_iterator(std::string const& str, std::size_t start, std::size_t size) :str_(str), start_(start), size_(size) {}
substring_iterator(substring_iterator&&) = default;
substring_iterator(substring_iterator const&) = default;
substring_iterator& operator=(substring_iterator&&) = default;
substring_iterator& operator=(substring_iterator const&) = default;
~substring_iterator() = default;
substring_iterator& operator++()
{
++start_;
return *this;
}
substring_iterator operator++(int)
{
auto ret = *this;
++start_;
return ret;
}
substring operator*()const
{
return substring{ str_,start_,size_ };
}
bool operator==(substring_iterator const& rhs)const
{
return &str_ == &str_ &&
start_ == rhs.start_&&
size_ == rhs.size_;
}
bool operator!=(substring_iterator const& rhs)const
{
return !rhs.operator==(*this);
}
};
}
class substring_adaptor
{
std::string const& str_;
std::size_t size_;
public:
substring_adaptor(std::string const& str, std::size_t size) :str_(str), size_(size) {}
substring_adaptor(substring_adaptor&&) = default;
substring_adaptor(substring_adaptor const&) = default;
substring_adaptor& operator=(substring_adaptor&&) = default;
substring_adaptor& operator=(substring_adaptor const&) = default;
~substring_adaptor() = default;
detail::substring_iterator begin()const
{
if (str_.size() < size_)
return detail::substring_iterator(str_, 0, 0);
return detail::substring_iterator(str_, 0, size_);
}
detail::substring_iterator end()const
{
if (str_.size() < size_)
return detail::substring_iterator(str_, 0, 0);
return detail::substring_iterator(str_, str_.size() - size_ + 1, size_);
}
};
}
namespace geometry
{
template<class Type>struct point
{
Type x, y;
};
template<class Type>auto make_point(Type x, Type y)
{
return point<Type>{x, y};
}
template<class Type>auto operator+(point<Type>const& lhs, point<Type>const& rhs)
{
return make_point(lhs.x + rhs.x, lhs.y + rhs.y);
}
template<class Type>auto operator-(point<Type>const& lhs, point<Type>const& rhs)
{
return make_point(lhs.x - rhs.x, lhs.y - rhs.y);
}
template<class Point>struct box
{
Point small, large;
};
template<class Point>auto make_box(Point a, Point b)
{
return box<Point>{
make_point(std::min(a.x, b.x), std::min(a.y, b.y)),
make_point(std::max(a.x, b.x), std::max(a.y, b.y))};
}
template<class Point>boost::optional<box<Point>> hit_check(box<Point> a, box<Point> b)
{
if (a.small.x > b.small.x)
std::swap(a, b);
if (a.large.x < b.small.x)
return boost::none;
auto small_x = b.small.x;
auto large_x = std::min(b.large.x, a.large.x);
if (a.small.y < b.small.y)
{
if (b.small.y < a.large.y)
return make_box(
make_point(small_x, b.small.y),
make_point(large_x, std::min(a.large.y, b.large.y)));
else
return boost::none;
}
else
{
if (a.small.y < b.large.y)
return make_box(
make_point(small_x, a.small.y),
make_point(large_x, std::min(a.large.y, b.large.y)));
else
return boost::none;
}
}
}
namespace iostream
{
namespace detail
{
template<class Type>struct read_t
{
static Type read()
{
Type t;
std::cin >> t;
return t;
}
};
template<class Lhs, class Rhs>struct read_t<std::pair<Lhs, Rhs>>
{
static std::pair<Lhs, Rhs> read()
{
Lhs lhs;
Rhs rhs;
std::cin >> lhs;
std::cin >> rhs;
return std::make_pair(lhs, rhs);
}
};
template<class Type>struct read_t<geometry::point<Type>>
{
static geometry::point<Type> read()
{
Type lhs, rhs;
std::cin >> lhs;
std::cin >> rhs;
return geometry::make_point(lhs, rhs);
}
};
template<class... Ts>struct read_t<std::tuple<Ts...>>
{
static void get(std::tuple<Ts...>& v, std::integral_constant<std::size_t, sizeof...(Ts)>)
{
}
template<std::size_t I>static void get(std::tuple<Ts...>& v, std::integral_constant<std::size_t, I>)
{
std::get<I>(v) = read_t<std::tuple_element_t<I, std::tuple<Ts...>>>::read();
return get(v, std::integral_constant<std::size_t, I + 1>());
}
static std::tuple<Ts...> read()
{
std::tuple<Ts...> v;
get(v, std::integral_constant<std::size_t, 0>());
return v;
}
};
}
template<class T>auto read()
{
return detail::read_t<T>::read();
}
template<class T>auto vector_read(uint64 N)
{
std::vector<T> vec;
vec.reserve(N + 1);
for (uint64 i = 0;i < N;++i)
{
vec.push_back(read<T>());
}
return vec;
}
}
namespace graph_traits
{
class graph
{
std::vector<int64> node_data;
std::vector<std::vector<std::pair<int, int64>>> edge_data;
public:
graph() = default;
graph(std::vector<int64>&& n) :node_data(std::move(n)), edge_data{}
{
edge_data.resize(node_data.size());
}
graph(std::size_t size) :node_data(size), edge_data{}
{
}
void resize(int size)
{
node_data.resize(size);
edge_data.resize(size);
}
void edge_reserve(int size)
{
for (auto& v : edge_data)
{
v.reserve(size);
}
}
void add_node(int64 data)
{
node_data.emplace_back(data);
edge_data.emplace_back();
}
void add_edge(int from, int to, int64 data)
{
edge_data[from].emplace_back(to, data);
}
std::vector<math::infinite_value<int64>> dijkstra(int from)const
{
struct compare
{
bool operator()(
std::pair<int, math::infinite_value<int64>>const& lhs,
std::pair<int, math::infinite_value<int64>>const& rhs)const
{
return lhs.second > rhs.second;
}
};
std::priority_queue<
std::pair<int, math::infinite_value<int64>>,
std::vector<std::pair<int, math::infinite_value<int64>>>,
compare>nodes;
std::vector<math::infinite_value<int64>> ret(node_data.size());
for (int i{};i < node_data.size();++i)
{
nodes.emplace(i, math::infinite_value<int64>());
}
nodes.emplace(from, int());
while (nodes.size())
{
auto p = nodes.top();
nodes.pop();
if (ret[p.first] <= p.second)
continue;
ret[p.first] = p.second;
for (auto const& d : edge_data[p.first])
{
nodes.emplace(d.first, std::min(ret[d.first], ret[p.first] + d.second));
}
}
return ret;
}
int64 operator[](int n)const
{
return node_data[n];
}
};
}
namespace detail
{
constexpr uint64 literal_upper(uint64 v)
{
return v == 1 ? 1 : 10 * literal_upper(v - 1);
}
}
constexpr uint64 operator"" _u(uint64 v)
{
return detail::literal_upper(v);
}
void Main(std::integral_constant<int, 1>);
void Main(std::integral_constant<int, 2>);
void Main(std::integral_constant<int, 3>);
void Main(std::integral_constant<int, 4>);
void Main(std::integral_constant<int, 5>);
#endif//テンプレートここまで
//ここを書き換える
constexpr int problem = 2;
//ここは書き換えない
int main()
{
std::cin.sync_with_stdio(false);
std::cout << std::setprecision(std::numeric_limits<long double>::digits10 + 1);
Main(std::integral_constant<int, problem>{});
}
void Main(std::integral_constant<int, 1>)
{
auto R = iostream::read<int>();
auto C = iostream::read<int>();
auto start = iostream::read<std::pair<int, int>>();
--start.first;
--start.second;
auto goal = iostream::read<std::pair<int, int>>();
--goal.first;
--goal.second;
boost::multi_array<bool, 2> maze(boost::extents[R][C]);
for (int i{};i < R;++i)
{
auto str = iostream::read<std::string>();
for (int j{};j < C;++j)
{
maze[i][j] = (str[j] == '.');
}
}
boost::multi_array<boost::optional<int>, 2> counts(boost::extents[R][C]);
std::queue<std::pair<std::pair<int, int>, int>> data;
data.emplace(start, 0);
while (!counts[goal.first][goal.second])
{
auto d = data.front();
data.pop();
if (counts[d.first.first][d.first.second] ||
!maze[d.first.first][d.first.second])
continue;
counts[d.first.first][d.first.second] = d.second;
data.emplace(std::make_pair(d.first.first - 1, d.first.second), d.second + 1);
data.emplace(std::make_pair(d.first.first + 1, d.first.second), d.second + 1);
data.emplace(std::make_pair(d.first.first, d.first.second - 1), d.second + 1);
data.emplace(std::make_pair(d.first.first, d.first.second + 1), d.second + 1);
}
std::cout << *counts[goal.first][goal.second] << std::endl;
}
void Main(std::integral_constant<int, 2>)
{
auto N = iostream::read<uint64>();
auto M = iostream::read<uint64>();
auto P = iostream::read<uint64>();
std::vector<uint64> mul;
while (true)
{
if (P == 0)
{
N = 1;
break;
}
else if (P == 1)
{
break;
}
else if (P == 2)
{
N *= N;
N %= M;
break;
}
else if (P % 2 == 1)
{
mul.push_back(N);
N *= N;
N %= M;
P /= 2;
}
else
{
N *= N;
N %= M;
P /= 2;
}
}
for (auto v : mul)
{
N *= v;
N %= M;
}
std::cout << N << std::endl;
}
void Main(std::integral_constant<int, 3>)
{
}
void Main(std::integral_constant<int, 4>)
{
}
void Main(std::integral_constant<int, 5>)
{
}
Submission Info
Submission Time |
|
Task |
B - n^p mod m |
User |
plasmaeffect |
Language |
C++14 (Clang 3.8.0) |
Score |
0 |
Code Size |
37673 Byte |
Status |
WA |
Exec Time |
11 ms |
Memory |
888 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 100 |
Status |
AC
|
|
Set Name |
Test Cases |
Sample |
|
All |
001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt |
Case Name |
Status |
Exec Time |
Memory |
001.txt |
AC |
11 ms |
888 KB |
002.txt |
AC |
4 ms |
256 KB |
003.txt |
AC |
4 ms |
256 KB |
004.txt |
AC |
4 ms |
256 KB |
005.txt |
AC |
4 ms |
256 KB |
006.txt |
AC |
4 ms |
256 KB |
007.txt |
AC |
4 ms |
256 KB |
008.txt |
AC |
4 ms |
256 KB |
009.txt |
AC |
4 ms |
256 KB |
010.txt |
AC |
4 ms |
256 KB |
011.txt |
AC |
4 ms |
256 KB |
012.txt |
AC |
4 ms |
256 KB |
013.txt |
AC |
4 ms |
256 KB |
014.txt |
AC |
4 ms |
256 KB |
015.txt |
AC |
4 ms |
256 KB |
016.txt |
AC |
4 ms |
256 KB |
017.txt |
AC |
4 ms |
256 KB |
018.txt |
AC |
4 ms |
256 KB |
019.txt |
AC |
4 ms |
256 KB |
020.txt |
AC |
4 ms |
256 KB |
021.txt |
WA |
4 ms |
256 KB |
022.txt |
WA |
4 ms |
256 KB |
023.txt |
AC |
4 ms |
256 KB |
024.txt |
WA |
4 ms |
256 KB |
025.txt |
AC |
4 ms |
256 KB |
026.txt |
AC |
4 ms |
256 KB |
027.txt |
AC |
4 ms |
256 KB |
sample_01.txt |
AC |
4 ms |
256 KB |
sample_02.txt |
AC |
4 ms |
256 KB |