結果
| 問題 |
No.2058 Binary String
|
| コンテスト | |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2022-08-26 22:50:57 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 78 ms / 2,000 ms |
| コード長 | 64,076 bytes |
| コンパイル時間 | 3,353 ms |
| コンパイル使用メモリ | 213,636 KB |
| 最終ジャッジ日時 | 2025-01-31 05:22:00 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 23 |
ソースコード
#include<bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
#define CIN( LL , A ) LL A; cin >> A
#define GETLINE( A ) string A; getline( cin , A )
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR )
#define FOR_LL( VAR , INITIAL , FINAL_PLUS_ONE ) for( ll VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ )
#define REPEAT( HOW_MANY_TIMES ) FOR_LL( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES )
#define RETURN( ANSWER ) cout << ( ANSWER ) << endl; return 0
#define DOUBLE( PRECISION , ANSWER ) cout << fixed << setprecision( PRECISION ) << ( ANSWER ) << endl; return 0
#define MIN( A , B ) A < B ? A : B;
#define MAX( A , B ) A < B ? B : A;
template <typename T> inline T Distance( const T& a , const T& b ){ return a < b ? b - a : a - b; }
// 自分のライブラリ（https://github.com/p-adic/cpp）よりソースコードをコピーして編集している。
using uint = unsigned int;
template <typename T> class VLArray;
template <typename T> class IteratorOfVLArray;
template <typename T> class ConstIteratorOfVLArray;
template <typename T>
class EntryOfVLArray
{
friend VLArray<T>;
friend IteratorOfVLArray<T>;
friend ConstIteratorOfVLArray<T>;
private:
T m_t;
EntryOfVLArray<T>* m_prev;
EntryOfVLArray<T>* m_next;
private:
inline EntryOfVLArray();
template <typename Arg> inline EntryOfVLArray( const Arg& );
template <typename Arg> inline EntryOfVLArray( const Arg& , EntryOfVLArray<T>* const& , EntryOfVLArray<T>* const& );
};
template <typename T> inline EntryOfVLArray<T>::EntryOfVLArray() : m_t() , m_prev( this ) , m_next( this ) {}
template <typename T> template <typename Arg> inline EntryOfVLArray<T>::EntryOfVLArray( const Arg& t ) : m_t( t ) , m_prev( this ) , m_next( this ) {}
template <typename T> template <typename Arg> inline EntryOfVLArray<T>::EntryOfVLArray( const Arg& t , EntryOfVLArray<T>* const& prev , EntryOfVLArray<T>* const& next ) : m_t( t ) , m_prev( prev ) , m_next( next ) {}
template <typename T> class EntryOfVLArray;
template <typename T> class ConstIteratorOfVLArray;
template <typename T> class VLArray;
template <typename T>
class IteratorOfVLArray
{
friend ConstIteratorOfVLArray<T>;
friend VLArray<T>;
private:
// ++の実装のためにはm_pをポインタへの参照にできない。
EntryOfVLArray<T>* m_p;
public:
inline IteratorOfVLArray( EntryOfVLArray<T>* const& ) noexcept;
inline IteratorOfVLArray( const IteratorOfVLArray<T>& ) noexcept;
// inline T& Access() const;
inline T& operator*() const;
inline T* operator->() const;
IteratorOfVLArray<T>& operator=( const IteratorOfVLArray<T>& ) noexcept;
inline void operator++( int );
inline void operator--( int );
};
template <typename T>
class ConstIteratorOfVLArray
{
friend VLArray<T>;
private:
const EntryOfVLArray<T>* m_p;
public:
inline ConstIteratorOfVLArray( EntryOfVLArray<T>* const& ) noexcept;
inline ConstIteratorOfVLArray( const ConstIteratorOfVLArray<T>& ) noexcept;
inline ConstIteratorOfVLArray( const IteratorOfVLArray<T>& ) noexcept;
inline const T& operator*() const;
inline const T* operator->() const;
ConstIteratorOfVLArray<T>& operator=( const ConstIteratorOfVLArray<T>& ) noexcept;
ConstIteratorOfVLArray<T>& operator=( const IteratorOfVLArray<T>& ) noexcept;
inline void operator++( int );
inline void operator--( int );
static inline bool Equal( const IteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;
static inline bool Equal( const ConstIteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;
static inline bool Equal( const IteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;
static inline bool Equal( const ConstIteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;
};
template <typename T> inline bool operator==( const IteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;
template <typename T> inline bool operator!=( const IteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;
template <typename T> inline bool operator==( const ConstIteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;
template <typename T> inline bool operator!=( const ConstIteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;
template <typename T> inline bool operator==( const IteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;
template <typename T> inline bool operator!=( const IteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;
template <typename T> inline bool operator==( const ConstIteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;
template <typename T> inline bool operator!=( const ConstIteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;
// IteratorOfVLArray
template <typename T> inline IteratorOfVLArray<T>::IteratorOfVLArray( EntryOfVLArray<T>* const& p ) noexcept : m_p( p ) {}
template <typename T> inline IteratorOfVLArray<T>::IteratorOfVLArray( const IteratorOfVLArray<T>& itr ) noexcept : m_p( itr.m_p ) {}
// template <typename T> inline T& IteratorOfVLArray<T>::Access() const { return Access( m_p ).m_t; }
template <typename T> inline T& IteratorOfVLArray<T>::operator*() const { return ( *m_p ).m_t; }
template <typename T> inline T* IteratorOfVLArray<T>::operator->() const { return &( *( *this ) ); }
template <typename T>
IteratorOfVLArray<T>& IteratorOfVLArray<T>::operator=( const IteratorOfVLArray<T>& itr ) noexcept
{
m_p = itr.m_p;
return *this;
}
template <typename T> inline void IteratorOfVLArray<T>::operator++( int ){ m_p = ( *m_p ).m_next; }
template <typename T> inline void IteratorOfVLArray<T>::operator--( int ){ m_p = ( *m_p ).m_prev; }
// ConstIteratorOfVLArray
template <typename T> inline ConstIteratorOfVLArray<T>::ConstIteratorOfVLArray( EntryOfVLArray<T>* const& p ) noexcept : m_p( p ) {}
template <typename T> inline ConstIteratorOfVLArray<T>::ConstIteratorOfVLArray( const ConstIteratorOfVLArray<T>& itr ) noexcept : m_p( itr.m_p ) {}
template <typename T> inline ConstIteratorOfVLArray<T>::ConstIteratorOfVLArray( const IteratorOfVLArray<T>& itr ) noexcept : m_p( itr.m_p ) {}
template <typename T> inline const T& ConstIteratorOfVLArray<T>::operator*() const { return ( *m_p ).m_t; };
template <typename T> inline const T* ConstIteratorOfVLArray<T>::operator->() const { return &( *( *this ) ); }
template <typename T>
ConstIteratorOfVLArray<T>& ConstIteratorOfVLArray<T>::operator=( const ConstIteratorOfVLArray<T>& itr ) noexcept
{
m_p = itr.m_p;
return *this;
}
template <typename T>
ConstIteratorOfVLArray<T>& ConstIteratorOfVLArray<T>::operator=( const IteratorOfVLArray<T>& itr ) noexcept
{
m_p = itr.m_p;
return *this;
}
template <typename T> inline void ConstIteratorOfVLArray<T>::operator++( int ) { m_p = ( *m_p ).m_next; }
template <typename T> inline void ConstIteratorOfVLArray<T>::operator--( int ) { m_p = ( *m_p ).m_prev; }
template <typename T> inline bool ConstIteratorOfVLArray<T>::Equal( const IteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept { return itr0.m_p == itr1.m_p; }
template <typename T> inline bool ConstIteratorOfVLArray<T>::Equal( const ConstIteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept { return itr0.m_p == itr1.m_p; }
template <typename T> inline bool ConstIteratorOfVLArray<T>::Equal( const IteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 ) noexcept { return itr0.m_p == itr1.m_p; }
template <typename T> inline bool ConstIteratorOfVLArray<T>::Equal( const ConstIteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 ) noexcept { return itr0.m_p == itr1.m_p; }
template <typename T> inline bool operator==( const IteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept { return ConstIteratorOfVLArray<T>::Equal( itr0 , itr1 ); }
template <typename T> inline bool operator!=( const IteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept { return !( itr0 == itr1 );}
template <typename T> inline bool operator==( const ConstIteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept { return ConstIteratorOfVLArray<T>::Equal( itr0 , itr1 ); }
template <typename T> inline bool operator!=( const ConstIteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept { return !( itr0 == itr1 );}
template <typename T> inline bool operator==( const IteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 ) noexcept { return ConstIteratorOfVLArray<T>::Equal( itr0 , itr1 ); }
template <typename T> inline bool operator!=( const IteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 ) noexcept { return !( itr0 == itr1 );}
template <typename T> inline bool operator==( const ConstIteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 ) noexcept { return ConstIteratorOfVLArray<T>::Equal( itr0 , itr1 ); }
template <typename T> inline bool operator!=( const ConstIteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 ) noexcept { return !( itr0 == itr1 );}
template <typename T>
class SingletonType
{
protected:
SingletonType() = default;
SingletonType( const SingletonType& ) = default;
virtual ~SingletonType() = default;
SingletonType& operator=( const SingletonType& ) = default;
public:
static T& GetUniqueObject();
};
template <typename T>
class SingletonOf :
public SingletonType<SingletonOf<T> >
{
friend SingletonType<SingletonOf<T> >;
private:
SingletonOf() = default;
SingletonOf( const SingletonOf& ) = default;
~SingletonOf() = default;
SingletonOf& operator=( const SingletonOf& ) = default;
public:
using type = T;
};
// Replace TYPE_NAME by a suitable typename.
/*
class TYPE_NAME :
public SingletonType<TYPE_NAME>
{
friend SingletonType<TYPE_NAME>;
private:
TYPE_NAME() = default;
TYPE_NAME( const TYPE_NAME& ) = default;
~TYPE_NAME() = default;
TYPE_NAME& operator=( const TYPE_NAME& ) = default;
};
*/
template <typename T> T& Object();
#include <typeinfo>
template <typename T>
T& SingletonType<T>::GetUniqueObject()
{
static T t;
return t;
}
template <typename T>
T& Object()
{
// if( ! is_base_of<SingletonType<T>,T>::value ){
// ERR_IMPUT( typeid( T ) );
// }
return T::GetUniqueObject();
}
template <int i>
class WrappedInt :
public SingletonType<WrappedInt<i> >
{
friend class SingletonType<WrappedInt<i> >;
private:
WrappedInt() = default;
WrappedInt( const WrappedInt& ) = default;
WrappedInt& operator=( const WrappedInt& ) = default;
static const int m_i;
public:
static int Get();
};
template <uint i>
class WrappedUInt :
public SingletonType<WrappedUInt<i> >
{
friend class SingletonType<WrappedUInt<i> >;
private:
WrappedUInt() = default;
WrappedUInt( const WrappedUInt& ) = default;
WrappedUInt& operator=( const WrappedUInt& ) = default;
static const uint m_i;
public:
static uint Get();
};
template <int i> const WrappedInt<i>& Wrap();
template <uint i> const WrappedUInt<i>& WrapU();
template <int i>
const int WrappedInt<i>::m_i = i;
template <uint i>
const uint WrappedUInt<i>::m_i = i;
template <int i>
int WrappedInt<i>::Get()
{
return m_i;
}
template <uint i>
uint WrappedUInt<i>::Get()
{
return m_i;
}
template <int i>
const WrappedInt<i>& Wrap()
{
return Object<WrappedInt<i> >();
}
template <uint i>
const WrappedUInt<i>& WrapU()
{
return Object<WrappedUInt<i> >();
}
class EmptySet
{
private:
EmptySet();
EmptySet( const EmptySet& );
EmptySet& operator=( const EmptySet& );
};
template <typename T> class VLArray;
template <typename N , typename T> class VLMatrix_Body;
template <typename T>
class VLMatrix_Body<WrappedUInt<1>,T>
{
public:
using type = VLArray<T>;
};
template <typename T>
class VLMatrix_Body<WrappedUInt<2>,T>
{
public:
using type = VLArray<typename VLMatrix_Body<WrappedUInt<1>,T>::type>;
};
template <typename T>
class VLMatrix_Body<WrappedUInt<3>,T>
{
public:
using type = VLArray<typename VLMatrix_Body<WrappedUInt<2>,T>::type>;
};
template <uint N , typename T>
using VLMatrix = typename VLMatrix_Body<WrappedUInt<N>,T>::type;
template <typename T> class IteratorOfVLArray;
template <typename T> class ConstIteratorOfVLArray;
template <typename Arg> class WrappedType;
template <typename T>
class VLArray
{
private:
EntryOfVLArray<T> m_e;
EntryOfVLArray<T>* const m_p_e;
uint m_size;
public:
// Tは引数0のコンストラクタを持つクラスのみ許容。
inline VLArray();
template <typename Arg1 , typename... Arg2> inline VLArray( const Arg1& , const Arg2&... );
inline VLArray( const VLArray<T>& );
// Tが引数0のコンストラクタを持たないクラスの場合に使用。
template <typename Arg> inline VLArray( const WrappedType<Arg>& t );
virtual ~VLArray();
VLArray<T>& operator=( const VLArray<T>& );
inline const uint& size() const noexcept;
inline void clear();
inline bool empty() const noexcept;
T& front();
const T& front() const;
T& back();
const T& back() const;
template <typename Arg> void push_back( const Arg& );
template <typename... Args> void push_back( const Args&... );
template <typename Arg> void push_front( const Arg& );
// 前から順にpush_frontする。
template <typename... Args> void push_front( const Args&... );
void pop_back();
void pop_front();
template <typename... Args> inline void Concatenate( const Args&... );
template <typename Arg> void Concatenate_back( const Arg& );
template <typename... Args> void Concatenate_back( const Args&... );
template <typename Arg> void Concatenate_front( const Arg& );
// 前から順にConcatenate_frontする。
template <typename... Args> void Concatenate_front( const Args&... );
using iterator = IteratorOfVLArray<T>;
using const_iterator = ConstIteratorOfVLArray<T>;
// *thisがconstである場合に確実にconst_iterator返しをするために、iterator返しは非constにする必要がある。
inline iterator begin() noexcept;
inline const_iterator begin() const noexcept;
inline iterator end() noexcept;
inline const_iterator end() const noexcept;
template <typename Arg> void insert( const iterator& , const Arg& );
template <typename Arg> void insert_front( const iterator& , const Arg& );
template <typename Arg> void insert_back( const iterator& , const Arg& );
iterator erase( iterator& );
iterator erase_back( iterator& );
iterator erase_front( iterator& );
T& operator[]( const uint& );
const T& operator[]( const uint& ) const;
VLArray<T> GetInitialSegment( const int& ) const;
VLArray<T> GetFinalSegment( const int& ) const;
bool CheckContain( const iterator& ) const noexcept;
bool CheckContain( const const_iterator& ) const noexcept;
string Display() const;
private:
template <typename Arg> inline int push_back_int( const Arg& );
template <typename Arg> inline int push_front_int( const Arg& );
template <typename Arg> inline int Concatenate_back_int( const Arg& );
template <typename Arg> inline int Concatenate_front_int( const Arg& );
template <typename... Args> static inline void ExpandParameterPack( const Args&... ) noexcept;
};
template <typename T> bool operator==( const VLArray<T>& , const VLArray<T>& );
template <typename T> inline bool operator!=( const VLArray<T>& , const VLArray<T>& );
template <typename T> VLArray<T> to_VLArray( const uint& , const T& );
template <typename T> inline VLMatrix<1,T> to_VLMatrix( const uint& , const T& );
template <typename T> inline VLMatrix<2,T> to_VLMatrix( const uint& , const uint& , const T& );
template <typename T> inline VLMatrix<3,T> to_VLMatrix( const uint& , const uint& , const uint& , const T& );
template <typename T , typename... Arg> VLArray<T> Frown( const Arg&... );
template <typename T> T Sum( const VLArray<T>& );
template <typename Arg>
class WrappedType
{
private:
Arg m_t;
public:
template <typename... ARGS> inline WrappedType( const ARGS&... args );
inline void Set( const Arg& t );
inline const Arg& Get() const noexcept;
};
template <typename... Types>
class WrappedTypes
{};
template <typename Arg> template <typename... ARGS> inline WrappedType<Arg>::WrappedType( const ARGS&... args ) : m_t( args... ) {}
template <typename Arg> inline void WrappedType<Arg>::Set( const Arg& t ){ m_t = t; }
template <typename Arg> inline const Arg& WrappedType<Arg>::Get() const noexcept { return m_t; }
template <typename T> inline VLArray<T>::VLArray() : m_e() , m_p_e( &m_e ) , m_size( 0 ) {}
template <typename T> template <typename Arg1 , typename... Arg2> inline VLArray<T>::VLArray( const Arg1& t0 , const Arg2&... t1 ) : VLArray() { push_back( t0 , t1... ); }
template <typename T> inline VLArray<T>::VLArray( const VLArray<T>& a ) : m_e( a.m_e.m_t ) , m_p_e( &m_e ) , m_size( 0 ) { Concatenate( a ); }
template <typename T> template <typename Arg> inline VLArray<T>::VLArray( const WrappedType<Arg>& t ) : m_e( t.Get() ) , m_p_e( &m_e ) , m_size( 0 ) {}
template <typename T> VLArray<T>::~VLArray() { clear(); }
template <typename T>
VLArray<T>& VLArray<T>::operator=( const VLArray<T>& a )
{
if( this != &a ){
clear();
Concatenate( a );
}
return *this;
}
template <typename T> inline const uint& VLArray<T>::size() const noexcept { return m_size; }
template <typename T> inline void VLArray<T>::clear(){ while( m_size > 0 ) pop_back(); }
template <typename T> inline bool VLArray<T>::empty() const noexcept { return m_size == 0; }
template <typename T>
T& VLArray<T>::front()
{
// if( m_size == 0 ){
// ERR_CALL;
// }
return m_e.m_next->m_t;
}
template <typename T>
const T& VLArray<T>::front() const
{
// if( m_size == 0 ){
// ERR_CALL;
// }
return m_e.m_next->m_t;
}
template <typename T>
T& VLArray<T>::back()
{
// if( m_size == 0 ){
// ERR_CALL;
// }
return m_e.m_prev->m_t;
}
template <typename T>
const T& VLArray<T>::back() const
{
// if( m_size == 0 ){
// ERR_CALL;
// }
return m_e.m_prev->m_t;
}
template <typename T> template <typename Arg>
void VLArray<T>::push_back( const Arg& t )
{
EntryOfVLArray<T>* p_e_prev = m_e.m_prev;
auto p = new EntryOfVLArray<T>( t , p_e_prev , m_p_e );
m_e.m_prev = p;
p_e_prev->m_next = p;
m_size++;
return;
}
template <typename T> template <typename... Args>
void VLArray<T>::push_back( const Args&... args )
{
VLArray<T> copy{};
// 関数の処理は後ろからなのでbackではなくfrontを使う。
ExpandParameterPack( copy.push_front_int( args )... );
Concatenate_back( copy );
return;
}
template <typename T> template <typename Arg> inline int VLArray<T>::push_back_int( const Arg& t ) { push_back( t ); return 0; }
template <typename T> template <typename Arg>
void VLArray<T>::push_front( const Arg& t )
{
EntryOfVLArray<T>* p_b = m_e.m_next;
auto p = new EntryOfVLArray<T>( t , m_p_e , p_b );
p_b->m_prev = p;
m_e.m_next = p;
m_size++;
return;
}
template <typename T> template <typename... Args>
void VLArray<T>::push_front( const Args&... args )
{
VLArray<T> copy{};
// 関数の処理は後ろからなのでfrontではなくbackを使う。
ExpandParameterPack( copy.push_back_int( args )... );
Concatenate_front( copy );
return;
}
template <typename T> template <typename Arg> inline int VLArray<T>::push_front_int( const Arg& t ) { push_front( t ); return 0; }
template <typename T>
void VLArray<T>::pop_back()
{
// if( m_size == 0 ){
// ERR_CALL;
// }
EntryOfVLArray<T>* p_e_prev = m_e.m_prev;
EntryOfVLArray<T>* p_e_prev_prev = p_e_prev->m_prev;
m_e.m_prev = p_e_prev_prev;
p_e_prev_prev->m_next = m_p_e;
delete p_e_prev;
m_size--;
return;
}
template <typename T>
void VLArray<T>::pop_front()
{
// if( m_size == 0 ){
// ERR_CALL;
// }
EntryOfVLArray<T>* p_b = m_e.m_next;
EntryOfVLArray<T>* p_b_next = ( *p_b ).m_next;
p_b_next->m_prev = m_p_e;
m_e.m_next = p_b_next;
delete p_b;
m_size--;
return;
}
template <typename T> template <typename... Args> inline void VLArray<T>::Concatenate( const Args&... args ) { Concatenate_back( args... ); }
template <typename T> template <typename Arg>
void VLArray<T>::Concatenate_back( const Arg& a )
{
const EntryOfVLArray<T>* p = a.m_p_e;
const uint& N = a.m_size;
for( uint n = 0 ; n < N ; n++ ){
p = p->m_next;
push_back( p->m_t );
}
return;
}
template <typename T> template <typename... Args>
void VLArray<T>::Concatenate_back( const Args&... args )
{
VLArray<T> copy{};
// 関数の処理は後ろからなのでbackではなくfrontを使う。
ExpandParameterPack( copy.Concatenate_front_int( args )... );
Concatenate_back( copy );
return;
}
template <typename T> template <typename Arg> inline int VLArray<T>::Concatenate_back_int( const Arg& a ) { Concatenate( a ); return 0; }
template <typename T> template <typename Arg>
void VLArray<T>::Concatenate_front( const Arg& a )
{
const EntryOfVLArray<T>* p = a.m_p_e;
const uint& N = a.m_size;
for( uint n = 0 ; n < N ; n++ ){
p = p->m_prev;
push_front( p->m_t );
}
return;
}
template <typename T> template <typename... Args>
void VLArray<T>::Concatenate_front( const Args&... args )
{
VLArray<T> copy{};
// 関数の処理は後ろからなのでfrontではなくbackを使う。
ExpandParameterPack( copy.Concatenate_back_int( args )... );
Concatenate_front( copy );
return;
}
template <typename T> template <typename Arg> inline int VLArray<T>::Concatenate_front_int( const Arg& a ) { Concatenate_front( a ); return 0; }
template <typename T> inline typename VLArray<T>::iterator VLArray<T>::begin() noexcept { return IteratorOfVLArray<T>( m_e.m_next ); }
template <typename T> inline typename VLArray<T>::const_iterator VLArray<T>::begin() const noexcept { return ConstIteratorOfVLArray<T>( m_e.m_next ); }
template <typename T> inline typename VLArray<T>::iterator VLArray<T>::end() noexcept { return IteratorOfVLArray<T>( m_p_e ); }
template <typename T> inline typename VLArray<T>::const_iterator VLArray<T>::end() const noexcept { return ConstIteratorOfVLArray<T>( m_p_e ); }
template <typename T> template <typename Arg> inline void VLArray<T>::insert( const typename VLArray<T>::iterator& itr , const Arg& t ) { insert_back( itr , t ); }
template <typename T> template <typename Arg>
void VLArray<T>::insert_front( const typename VLArray<T>::iterator& itr , const Arg& t )
{
// if( ! CheckContain( itr ) ){
// ERR_IMPUT( itr , t );
// }
if( itr == begin() ){
push_front( t );
} else {
EntryOfVLArray<T>* p1 = itr.m_p;
EntryOfVLArray<T>* p0 = p1->m_prev;
auto p = new EntryOfVLArray<T>( t , p0 , p1 );
p0->m_next = p;
p1->m_prev = p;
m_size++;
}
return;
}
template <typename T> template <typename Arg>
void VLArray<T>::insert_back( const typename VLArray<T>::iterator& itr , const Arg& t )
{
// if( ! CheckContain( itr ) ){
// ERR_IMPUT( itr , t );
// }
EntryOfVLArray<T>* p0 = itr.m_p;
EntryOfVLArray<T>* p1 = p0->m_next;
auto p = new EntryOfVLArray<T>( t , p0 , p1 );
p1->m_prev = p;
p0->m_next = p;
m_size++;
return;
}
template <typename T> inline typename VLArray<T>::iterator VLArray<T>::erase( typename VLArray<T>::iterator& itr ) { return erase_back( itr ); }
template <typename T>
typename VLArray<T>::iterator VLArray<T>::erase_back( typename VLArray<T>::iterator& itr )
{
// if( ! CheckContain( itr ) ){
// ERR_IMPUT( itr );
// }
EntryOfVLArray<T>* p = itr.m_p;
EntryOfVLArray<T>* p0 = p->m_prev;
EntryOfVLArray<T>* p1 = p->m_next;
p0->m_next = p1;
p1->m_prev = p0;
itr++;
delete p;
m_size--;
return itr;
}
template <typename T>
typename VLArray<T>::iterator VLArray<T>::erase_front( typename VLArray<T>::iterator& itr )
{
// if( ! CheckContain( itr ) ){
// ERR_IMPUT( itr );
// }
EntryOfVLArray<T>* p = itr.m_p;
EntryOfVLArray<T>* p0 = p->m_prev;
EntryOfVLArray<T>* p1 = p->m_next;
p0->m_next = p1;
p1->m_prev = p0;
itr--;
delete p;
m_size--;
return itr;
}
template <typename T>
T& VLArray<T>::operator[]( const uint& i )
{
// if( i >= m_size ){
// ERR_IMPUT( i );
// }
if( i < m_size / 2 ){
EntryOfVLArray<T>* p = m_e.m_next;
for( uint n = 0 ; n < i ; n++ ){
p = p->m_next;
}
return p->m_t;
}
EntryOfVLArray<T>* p = m_e.m_prev;
for( uint n = m_size - 1 ; n > i ; n-- ){
p = p->m_prev;
}
return p->m_t;
}
template <typename T>
const T& VLArray<T>::operator[]( const uint& i ) const
{
// if( i >= m_size ){
// ERR_IMPUT( i );
// }
if( i < m_size / 2 ){
EntryOfVLArray<T>* p = m_e.m_next;
for( uint n = 0 ; n < i ; n++ ){
p = p->m_next;
}
return p->m_t;
}
EntryOfVLArray<T>* p = m_e.m_prev;
for( uint n = m_size - 1 ; n > i ; n-- ){
p = p->m_prev;
}
return p->m_t;
}
template <typename T>
VLArray<T> VLArray<T>::GetInitialSegment( const int& n ) const
{
const int N = (int)m_size;
int M;
if( N <= n ){
M = N;
} else {
if( 0 <= n ){
M = n;
} else {
M = N + n;
}
}
VLArray<T> b{};
const_iterator itr = begin();
for( int m = 1 ; m <= M ; m++ ){
b.push_back( *itr );
itr++;
}
return b;
}
template <typename T>
VLArray<T> VLArray<T>::GetFinalSegment( const int& n ) const
{
const int N = (int)m_size;
int M;
if( N <= n ){
M = N;
} else {
if( 0 <= n ){
M = n;
} else {
M = N + n;
}
}
VLArray<T> b{};
const_iterator itr = end();
for( int m = 1 ; m <= M ; m++ ){
itr--;
b.push_front( *itr );
}
return b;
}
template <typename T>
bool VLArray<T>::CheckContain( const iterator& itr ) const noexcept
{
for( auto itr_b = begin() , itr_e = end() ; itr_b != itr_e ; itr_b++ ){
if( itr == itr_b ){
return true;
}
}
return false;
}
template <typename T>
bool VLArray<T>::CheckContain( const const_iterator& itr ) const noexcept
{
for( auto itr_b = begin() , itr_e = end() ; itr_b != itr_e ; itr_b++ ){
if( itr == itr_b ){
return true;
}
}
return false;
}
template <typename T>
string VLArray<T>::Display() const
{
string s = "(";
EntryOfVLArray<T>* p = m_p_e;
for( uint n = 0 ; n < m_size ; n++ ){
p = p->m_next;
if( n > 0 ){
s += ",";
}
s += to_string( p->m_t );
}
s += ")";
return s;
}
template <typename T> template <typename... Args> inline void VLArray<T>::ExpandParameterPack( const Args&... ) noexcept {};
template <typename T>
bool operator==( const VLArray<T>& a1 , const VLArray<T>& a2 )
{
auto itr1 = a1.begin();
auto end1 = a1.end();
auto itr2 = a2.begin();
auto end2 = a2.end();
while( itr1 != end1 && itr2 != end2 ){
if( *itr1 != *itr2 ){
return false;
}
itr1++;
itr2++;
}
return ( itr1 == end1 ) && ( itr2 == end2 );
}
template <typename T> inline bool operator!=( const VLArray<T>& a1 , const VLArray<T>& a2 ) { return !( a1 == a2 ); }
template <typename T> VLArray<T> to_VLArray( const uint& N , const T& t )
{
auto a = VLArray<T>();
for( uint n = 0 ; n < N ; n++ ){
a.push_back( t );
}
return a;
}
template <typename T> inline VLMatrix<1,T> to_VLMatrix( const uint& N , const T& t ){ return to_VLArray( N , t ); }
template <typename T> inline VLMatrix<2,T> to_VLMatrix( const uint& N0 , const uint& N1 , const T& t ){ return to_VLArray( N1 , to_VLArray( N0 , t ) ); }
template <typename T> inline VLMatrix<3,T> to_VLMatrix( const uint& N0 , const uint& N1 , const uint& N2 , const T& t){ return to_VLArray( N2 , to_VLMatrix( N0 , N1 , t ) ); }
template <typename T , typename... Arg>
VLArray<T> Frown( const Arg&... args )
{
VLArray<T> a{};
a.Concatenate( args... );
return a;
}
template <typename T> T Sum( const VLArray<T>& a )
{
T t{};
for( auto itr = a.begin() , end = a.end() ; itr != end ; itr++ ){
t += *itr;
}
return t;
}
template <typename INT>
INT Residue( const INT& M , const INT& n ) noexcept;
template <typename INT>
INT Residue( const INT& M , const INT& n ) noexcept
{
if( M == 0 ){
return 0;
}
const INT M_abs = ( M > 0 ? M : -M );
if( n < 0 ){
const INT n_abs = -n;
const INT res = n_abs % M_abs;
return res == 0 ? res : M_abs - res;
}
return n % M_abs;
}
using INT_TYPE_FOR_ADIC_INT = long long int;
template <INT_TYPE_FOR_ADIC_INT P , INT_TYPE_FOR_ADIC_INT LENGTH = 0>
class AdicInt
{
private:
VLArray<INT_TYPE_FOR_ADIC_INT> m_expansion;
INT_TYPE_FOR_ADIC_INT m_n;
public:
inline AdicInt( const INT_TYPE_FOR_ADIC_INT& n ) noexcept;
inline const VLArray<INT_TYPE_FOR_ADIC_INT>& GetExpansion() const noexcept;
inline const INT_TYPE_FOR_ADIC_INT& GetValue() const noexcept;
static const VLArray<INT_TYPE_FOR_ADIC_INT>& Expand( const INT_TYPE_FOR_ADIC_INT& n ) noexcept;
};
template <INT_TYPE_FOR_ADIC_INT P , INT_TYPE_FOR_ADIC_INT LENGTH> inline AdicInt<P,LENGTH>::AdicInt( const INT_TYPE_FOR_ADIC_INT& n ) noexcept : m_expansion( Expand( n ) ) , m_n( n ) {}
template <INT_TYPE_FOR_ADIC_INT P , INT_TYPE_FOR_ADIC_INT LENGTH> inline const VLArray<INT_TYPE_FOR_ADIC_INT>& AdicInt<P,LENGTH>::GetExpansion() const noexcept { return m_expansion; }
template <INT_TYPE_FOR_ADIC_INT P , INT_TYPE_FOR_ADIC_INT LENGTH> inline const INT_TYPE_FOR_ADIC_INT& AdicInt<P,LENGTH>::GetValue() const noexcept { return m_n; }
template <INT_TYPE_FOR_ADIC_INT P , INT_TYPE_FOR_ADIC_INT LENGTH>
const VLArray<INT_TYPE_FOR_ADIC_INT>& AdicInt<P,LENGTH>::Expand( const INT_TYPE_FOR_ADIC_INT& n ) noexcept
{
static VLArray<INT_TYPE_FOR_ADIC_INT> memory_n{};
static VLArray<VLArray<INT_TYPE_FOR_ADIC_INT> > memory_answer{};
if( P == 0 ){
// ダミー
return memory_n;
}
auto itr_n = memory_n.begin() , end_n = memory_n.end();
auto itr_answer = memory_answer.begin();
while( itr_n != end_n ){
if( *itr_n == n ){
return *itr_answer;
}
itr_n++;
itr_answer++;
}
INT_TYPE_FOR_ADIC_INT n_copy = n;
VLArray<INT_TYPE_FOR_ADIC_INT> answer{};
if( LENGTH == 0 ){
for( INT_TYPE_FOR_ADIC_INT i = 0 ; n_copy != 0 ; i++ ){
const INT_TYPE_FOR_ADIC_INT d = Residue<INT_TYPE_FOR_ADIC_INT>( P , n_copy );
answer.push_back( d );
n_copy -= d;
n_copy /= P;
}
} else {
for( INT_TYPE_FOR_ADIC_INT i = 0 ; i < LENGTH && n_copy != 0 ; i++ ){
const INT_TYPE_FOR_ADIC_INT d = Residue<INT_TYPE_FOR_ADIC_INT>( P , n_copy );
answer.push_back( d );
n_copy -= d;
n_copy /= P;
}
}
memory_n.push_back( n );
memory_answer.push_back( answer );
return memory_answer.back();
}
// init * ( t ^ num )
template <typename T , typename UINT>
T Power( const T& t , const UINT& num , const T& init = 1 , const bool& for_right_multiplication = true , const string& method = "normal" );
template <typename T , typename UINT> inline T PowerNormalMethod( const T& t , const UINT& num , const T& init = 1 , const bool& for_right_multiplication = true );
template <typename T , typename UINT>
T PowerBinaryMethod( const T& t , const UINT& num , const T& init = 1 , const bool& for_right_multiplication = true );
// 単なる２乗だが、T次第ではオーバーロードしてより高速なものに置き換える
template <typename T> inline T Square( const T& t );
// PowerBinaryMetodの呼び出しは部分特殊化ではなくオーバーロードで処理できるようにするためにPowerBinaryMethod<T,UINT>とはしない。
template <typename T , typename UINT>
inline T Power( const T& t , const UINT& num , const T& init , const bool& for_right_multiplication , const string& method ) { return method == "binary" ? PowerBinaryMethod( t , num , init , for_right_multiplication ) : PowerNormalMethod( t , num , init , for_right_multiplication ); }
template <typename T , typename UINT> inline T PowerNormalMethod( const T& t , const UINT& num , const T& init , const bool& for_right_multiplication ) { return num == 0 ? init : ( for_right_multiplication ? PowerNormalMethod( t , num - 1 , init ) * t : t * PowerNormalMethod( t , num - 1 , init ) ); }
template <typename T , typename UINT>
T PowerBinaryMethod( const T& t , const UINT& num , const T& init , const bool& for_right_multiplication )
{
const VLArray<UINT>& num_binary = AdicInt<2>::Expand( num );
T answer = init;
T power = t;
for( auto itr = num_binary.begin() , end = num_binary.end() ; itr != end ; itr++ ){
if( *itr == 1 ){
answer = for_right_multiplication ? answer * power : power * answer;
}
// 部分特殊化ではなくオーバーロードで処理できるようにするためにSquare<T>としない。
power = Square( power );
}
return answer;
}
template <typename T> inline T Square( const T& t ) { return t * t; }
using INT_TYPE_FOR_MOD = long long int;
// ここをtempate <typename INT , INT M>などにしてしまうとoperator+などを呼び出す際に型推論に失敗する。整数型を変えたい時はINT_TYPE_FOR_MODの型エイリアスを変更する。
template <INT_TYPE_FOR_MOD M>
class Mod
{
protected:
INT_TYPE_FOR_MOD m_n;
INT_TYPE_FOR_MOD m_inv;
public:
inline Mod() noexcept;
inline Mod( const INT_TYPE_FOR_MOD& n ) noexcept;
inline Mod( const Mod<M>& n ) noexcept;
inline Mod<M>& operator=( const INT_TYPE_FOR_MOD& n ) noexcept;
Mod<M>& operator=( const Mod<M>& n ) noexcept;
Mod<M>& operator+=( const INT_TYPE_FOR_MOD& n ) noexcept;
inline Mod<M>& operator+=( const Mod<M>& n ) noexcept;
inline Mod<M>& operator-=( const INT_TYPE_FOR_MOD& n ) noexcept;
inline Mod<M>& operator-=( const Mod<M>& n ) noexcept;
Mod<M>& operator*=( const INT_TYPE_FOR_MOD& n ) noexcept;
Mod<M>& operator*=( const Mod<M>& n ) noexcept;
// INT_TYPE_FOR_MODでの割り算ではないことに注意
virtual Mod<M>& operator/=( const INT_TYPE_FOR_MOD& n );
virtual Mod<M>& operator/=( const Mod<M>& n );
Mod<M>& operator%=( const INT_TYPE_FOR_MOD& n );
inline Mod<M>& operator%=( const Mod<M>& n );
// 前置++/--を使うつもりがないので後置++/--と同じものとして定義する
inline Mod<M>& operator++() noexcept;
inline Mod<M>& operator++( int ) noexcept;
inline Mod<M>& operator--() noexcept;
inline Mod<M>& operator--( int ) noexcept;
inline const INT_TYPE_FOR_MOD& Represent() const noexcept;
void Invert() noexcept;
bool CheckInvertible() noexcept;
bool IsSmallerThan( const INT_TYPE_FOR_MOD& n ) const noexcept;
bool IsBiggerThan( const INT_TYPE_FOR_MOD& n ) const noexcept;
};
template <INT_TYPE_FOR_MOD M> inline bool operator==( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator==( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator==( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator==( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator!=( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator!=( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator!=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator!=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator<( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator<( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator<( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator<=( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator<=( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator<=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator<=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator>( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator>( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator>( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator>( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator>=( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator>=( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator>=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator>=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> Mod<M> operator+( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> Mod<M> operator+( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> Mod<M> operator+( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline Mod<M> operator-( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> Mod<M> operator-( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> Mod<M> operator-( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> Mod<M> operator*( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> Mod<M> operator*( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> Mod<M> operator*( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> Mod<M> operator/( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 );
template <INT_TYPE_FOR_MOD M> Mod<M> operator/( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 );
template <INT_TYPE_FOR_MOD M> Mod<M> operator/( const Mod<M>& n0 , const Mod<M>& n1 );
template <INT_TYPE_FOR_MOD M> Mod<M> operator%( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 );
template <INT_TYPE_FOR_MOD M> inline Mod<M> operator%( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 );
template <INT_TYPE_FOR_MOD M> inline Mod<M> operator%( const Mod<M>& n0 , const Mod<M>& n1 );
template <INT_TYPE_FOR_MOD M> Mod<M> Inverse( const Mod<M>& n );
template <INT_TYPE_FOR_MOD M> Mod<M> Power( const Mod<M>& n , const INT_TYPE_FOR_MOD& p , const string& method = "normal" );
template <> inline Mod<2> Power( const Mod<2>& n , const INT_TYPE_FOR_MOD& p , const string& method );
// M乗が1になるよう定義されていることに注意
template <INT_TYPE_FOR_MOD M> inline Mod<M> Power( const Mod<M>& n , const Mod<M>& p , const string& method = "normal" );
template <> inline Mod<2> Power( const Mod<2>& n , const Mod<2>& p , const string& method );
// ../Power/a_Body.hppにて定義
template <typename T> inline T Square( const T& t );
template <> inline Mod<2> Square<Mod<2> >( const Mod<2>& t );
void LazyEvaluationOfModularInverse( const INT_TYPE_FOR_MOD& M , const INT_TYPE_FOR_MOD& n , INT_TYPE_FOR_MOD& m );
template <INT_TYPE_FOR_MOD M> inline Mod<M>::Mod() noexcept : m_n( 0 ) , m_inv( M ){}
template <INT_TYPE_FOR_MOD M> inline Mod<M>::Mod( const INT_TYPE_FOR_MOD& n ) noexcept : m_n( Residue<INT_TYPE_FOR_MOD>( M , n ) ) , m_inv( 0 ){}
template <INT_TYPE_FOR_MOD M> inline Mod<M>::Mod( const Mod<M>& n ) noexcept : m_n( n.m_n ) , m_inv( 0 ){}
template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator=( const INT_TYPE_FOR_MOD& n ) noexcept { return operator=( Mod<M>( n ) ); }
template <INT_TYPE_FOR_MOD M>
Mod<M>& Mod<M>::operator=( const Mod<M>& n ) noexcept
{
m_n = n.m_n;
m_inv = n.m_inv;
return *this;
}
template <INT_TYPE_FOR_MOD M>
Mod<M>& Mod<M>::operator+=( const INT_TYPE_FOR_MOD& n ) noexcept
{
m_n = Residue<INT_TYPE_FOR_MOD>( M , m_n + n );
m_inv = 0;
return *this;
}
template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator+=( const Mod<M>& n ) noexcept { return operator+=( n.m_n ); };
template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator-=( const INT_TYPE_FOR_MOD& n ) noexcept { return operator+=( -n ); }
template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator-=( const Mod<M>& n ) noexcept { return operator-=( n.m_n ); }
template <INT_TYPE_FOR_MOD M>
Mod<M>& Mod<M>::operator*=( const INT_TYPE_FOR_MOD& n ) noexcept
{
m_n = Residue<INT_TYPE_FOR_MOD>( M , m_n * n );
m_inv = 0;
return *this;
}
template <INT_TYPE_FOR_MOD M>
Mod<M>& Mod<M>::operator*=( const Mod<M>& n ) noexcept
{
m_n = Residue<INT_TYPE_FOR_MOD>( M , m_n * n.m_n );
if( m_inv == 0 || n.m_inv == 0 ){
m_inv = 0;
} else if( m_inv == M || n.m_inv == M ){
m_inv = M;
} else {
Residue<INT_TYPE_FOR_MOD>( M , m_inv * n.m_inv );
}
return *this;
}
// 仮想関数なのでinline指定しない。
template <INT_TYPE_FOR_MOD M>
Mod<M>& Mod<M>::operator/=( const INT_TYPE_FOR_MOD& n )
{
return operator/=( Mod<M>( n ) );
}
template <INT_TYPE_FOR_MOD M>
Mod<M>& Mod<M>::operator/=( const Mod<M>& n )
{
return operator*=( Inverse( n ) );
}
template <INT_TYPE_FOR_MOD M>
Mod<M>& Mod<M>::operator%=( const INT_TYPE_FOR_MOD& n )
{
m_n %= Residue<INT_TYPE_FOR_MOD>( M , n );
m_inv = 0;
return *this;
}
template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator%=( const Mod<M>& n ) { return operator%=( n.m_n ); }
template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator++() noexcept { return operator+=( 1 ); }
template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator++( int ) noexcept { return operator++(); }
template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator--() noexcept { return operator-=( 1 ); }
template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator--( int ) noexcept { return operator-=(); }
template <INT_TYPE_FOR_MOD M> inline const INT_TYPE_FOR_MOD& Mod<M>::Represent() const noexcept { return m_n; }
template <INT_TYPE_FOR_MOD M>
void Mod<M>::Invert() noexcept
{
if( CheckInvertible() ){
INT_TYPE_FOR_MOD i = m_inv;
m_inv = m_n;
m_n = i;
} else {
// m_nがMになるのはここの処理に限るのでRepresent()の値を参照することで例外処理可能
m_n = M;
m_inv = M;
}
return;
}
template <INT_TYPE_FOR_MOD M>
bool Mod<M>::CheckInvertible() noexcept
{
if( m_inv == 0 ){
LazyEvaluationOfModularInverse( M , m_n , m_inv );
}
return m_inv != M;
}
template <INT_TYPE_FOR_MOD M> inline bool Mod<M>::IsSmallerThan( const INT_TYPE_FOR_MOD& n ) const noexcept { return m_n < Residue<INT_TYPE_FOR_MOD>( M , n ); }
template <INT_TYPE_FOR_MOD M> inline bool Mod<M>::IsBiggerThan( const INT_TYPE_FOR_MOD& n ) const noexcept { return m_n > Residue<INT_TYPE_FOR_MOD>( M , n ); }
template <INT_TYPE_FOR_MOD M> inline bool operator==( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { return n0 == Mod<M>( n1 ); }
template <INT_TYPE_FOR_MOD M> inline bool operator==( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return Mod<M>( n0 ) == n0; }
template <INT_TYPE_FOR_MOD M> inline bool operator==( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return n0.Represent() == n1.Represent(); }
template <INT_TYPE_FOR_MOD M> inline bool operator!=( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { return !( n0 == n1 ); }
template <INT_TYPE_FOR_MOD M> inline bool operator!=( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return !( n0 == n1 ); }
template <INT_TYPE_FOR_MOD M> inline bool operator!=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return !( n0 == n1 ); }
template <INT_TYPE_FOR_MOD M> inline bool operator<( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { return n0.IsSmallerThan( n1 ); }
template <INT_TYPE_FOR_MOD M> inline bool operator<( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return n1.IsBiggerThan( n0 ); }
template <INT_TYPE_FOR_MOD M> inline bool operator<( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return n0.Represent() < n1.Represent(); }
template <INT_TYPE_FOR_MOD M> inline bool operator<=( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { return !( n1 < n0 ); }
template <INT_TYPE_FOR_MOD M> inline bool operator<=( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return !( n1 < n0 ); }
template <INT_TYPE_FOR_MOD M> inline bool operator<=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return !( n1 < n0 ); }
template <INT_TYPE_FOR_MOD M> inline bool operator>( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { return n1 < n0; }
template <INT_TYPE_FOR_MOD M> inline bool operator>( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return n1 < n0; }
template <INT_TYPE_FOR_MOD M> inline bool operator>( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return n1 < n0; }
template <INT_TYPE_FOR_MOD M> inline bool operator>=( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { return !( n0 < n1 ); }
template <INT_TYPE_FOR_MOD M> inline bool operator>=( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return !( n0 < n1 ); }
template <INT_TYPE_FOR_MOD M> inline bool operator>=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return !( n0 < n1 ); }
template <INT_TYPE_FOR_MOD M>
Mod<M> operator+( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept
{
auto n = n0;
n += n1;
return n;
}
template <INT_TYPE_FOR_MOD M> inline Mod<M> operator+( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return n1 + n0; }
template <INT_TYPE_FOR_MOD M> inline Mod<M> operator+( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return n0 + n1.Represent(); }
template <INT_TYPE_FOR_MOD M> inline Mod<M> operator-( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { return n0 + ( -n1 ); }
template <INT_TYPE_FOR_MOD M> inline Mod<M> operator-( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return Mod<M>( n0 - n1.Represent() ); }
template <INT_TYPE_FOR_MOD M> inline Mod<M> operator-( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return n0 - n1.Represent(); }
template <INT_TYPE_FOR_MOD M>
Mod<M> operator*( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept
{
auto n = n0;
n *= n1;
return n;
}
template <INT_TYPE_FOR_MOD M> inline Mod<M> operator*( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return n1 * n0; }
template <INT_TYPE_FOR_MOD M>
Mod<M> operator*( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept
{
auto n = n0;
n *= n1;
return n;
}
template <INT_TYPE_FOR_MOD M> inline Mod<M> operator/( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) { return n0 / Mod<M>( n1 ); }
template <INT_TYPE_FOR_MOD M> inline Mod<M> operator/( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) { return Mod<M>( n0 ) / n1; }
template <INT_TYPE_FOR_MOD M>
Mod<M> operator/( const Mod<M>& n0 , const Mod<M>& n1 )
{
auto n = n0;
n /= n1;
return n;
}
template <INT_TYPE_FOR_MOD M>
Mod<M> operator%( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 )
{
auto n = n0;
n %= n1;
return n;
}
template <INT_TYPE_FOR_MOD M> inline Mod<M> operator%( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) { return Mod<M>( n0 ) % n1.Represent(); }
template <INT_TYPE_FOR_MOD M> inline Mod<M> operator%( const Mod<M>& n0 , const Mod<M>& n1 ) { return n0 % n1.Represent(); }
template <INT_TYPE_FOR_MOD M>
Mod<M> Inverse( const Mod<M>& n )
{
auto n_copy = n;
n_copy.Invert();
return n_copy;
}
template <INT_TYPE_FOR_MOD M>
Mod<M> Power( const Mod<M>& n , const INT_TYPE_FOR_MOD& p , const string& method )
{
if( p >= 0 ){
return Power<Mod<M>,INT_TYPE_FOR_MOD>( n , p , 1 , true , true , method );
}
return Inverse( Power<M>( n , -p , method ) );
}
template <> inline Mod<2> Power( const Mod<2>& n , const INT_TYPE_FOR_MOD& p , const string& method ) { return p == 0 ? 1 : n; }
template <INT_TYPE_FOR_MOD M> inline Mod<M> Power( const Mod<M>& n , const Mod<M>& p , const string& method ) { return Power<Mod<M>,INT_TYPE_FOR_MOD>( n , p.Represent() , method ); }
template <> inline Mod<2> Power( const Mod<2>& n , const Mod<2>& p , const string& method ) { return p == 0 ? 1 : n; }
template <> inline Mod<2> Square<Mod<2> >( const Mod<2>& t ) { return t; }
void LazyEvaluationOfModularInverse( const INT_TYPE_FOR_MOD& M , const INT_TYPE_FOR_MOD& n , INT_TYPE_FOR_MOD& m )
{
static VLArray<INT_TYPE_FOR_MOD> memory_M{};
// vectorでなくVLArrayだと引数が小さい順に呼び出した時の計算量がO(1)からO(n)に跳ね上がってしまう。
static VLArray<vector<INT_TYPE_FOR_MOD> > memory_inverse{};
auto itr_M = memory_M.begin() , end_M = memory_M.end();
auto itr_inverse = memory_inverse.begin();
vector<INT_TYPE_FOR_MOD>* p_inverse = nullptr;
while( itr_M != end_M && p_inverse == nullptr ){
if( *itr_M == M ){
p_inverse = &( *itr_inverse );
}
itr_M++;
itr_inverse++;
}
if( p_inverse == nullptr ){
memory_M.push_front( M );
memory_inverse.push_front( vector<INT_TYPE_FOR_MOD>() );
p_inverse = &( memory_inverse.front() );
p_inverse->push_back( M );
}
const INT_TYPE_FOR_MOD size = p_inverse->size();
for( INT_TYPE_FOR_MOD i = size ; i <= n ; i++ ){
p_inverse->push_back( 0 );
}
INT_TYPE_FOR_MOD& n_inv = ( *p_inverse )[n];
if( n_inv != 0 ){
m = n_inv;
return;
}
const INT_TYPE_FOR_MOD M_abs = M >= 0 ? M : -M;
const INT_TYPE_FOR_MOD n_sub = M_abs % n;
INT_TYPE_FOR_MOD n_sub_inv = ( *p_inverse )[n_sub];
if( n_sub_inv == 0 ){
LazyEvaluationOfModularInverse( M , n_sub , n_sub_inv );
}
if( n_sub_inv != M ){
n_inv = M_abs - ( ( n_sub_inv * ( M_abs / n ) ) % M_abs );
m = n_inv;
return;
}
for( INT_TYPE_FOR_MOD i = 1 ; i < M_abs ; i++ ){
if( ( n * i ) % M_abs == 1 ){
n_inv = i;
m = n_inv;
return;
}
}
n_inv = M;
m = n_inv;
return;
}
// 階乗（INT = Mod<M>の時にMでの値が1であることに注意）
template <typename INT> inline INT Factorial( const INT& n , const INT& n_min = 1 , const string& mode = "normal" );
// modular階乗（INT1 = Mod<M>の時にMでの値が0であることに注意）
template <typename INT1 , typename INT2> inline INT1 ModularFactorial( const INT2& n , const INT2& n_min = 1 , const string& mode = "normal" );
// 再帰式（呼び出し順によっては再帰深度が大きい）
template <typename INT1 , typename INT2>
const INT1& ModularFactorialNormalMethod( const INT2& n );
template <typename INT1 , typename INT2>
const INT1& ModularFactorialNormalMethod( const INT2& n , const INT2& n_min );
template <typename INT1 , typename INT2>
const INT1& ModularFactorialNormalMethod_Body( const INT2& n , const INT2& n_min );
// ループ
template <typename INT1 , typename INT2>
INT1 ModularFactorialLoopMethod( const INT2& n , const INT2& n_min = 1 );
// modular階乗の逆数（INT1 = Mod<M>の時にMでの値がサポート外であることに注意）
template <typename INT1 , typename INT2> inline INT1 ModularFactorialInverse( const INT2& n , const INT2& n_min = 1 , const string& mode = "normal" );
// 再帰式（呼び出し順によっては再帰深度が大きい）
template <typename INT1 , typename INT2>
const INT1& ModularFactorialInverseNormalMethod( const INT2& n );
template <typename INT1 , typename INT2>
const INT1& ModularFactorialInverseNormalMethod( const INT2& n , const INT2& n_min );
template <typename INT1 , typename INT2>
const INT1& ModularFactorialInverseNormalMethod_Body( const INT2& n , const INT2& n_min );
// ループ
template <typename INT1 , typename INT2>
INT1 ModularFactorialInverseLoopMethod( const INT2& n , const INT2& n_min = 1 );
// 場合の数
template <typename INT>
INT Combination( const INT& n , const INT& m , const string& mode = "normal" );
// 再帰式（呼び出し順によっては再帰深度が大きい）
template <typename INT>
const INT& CombinationNormalMethod( const INT& n , const INT& m );
// ループ（割り算回数が大きい）
template <typename INT>
INT CombinationLoopMethod( const INT& n , const INT& m );
// 階乗の比（modular演算でない時はオーバーフローしやすい）
template <typename INT> inline INT CombinationFactorialNormalMethod( const INT& n , const INT& m );
template <typename INT> inline INT CombinationFactorialLoopMethod( const INT& n , const INT& m );
template <typename INT> inline INT CombinationModularFactorialInverseNormalMethod( const INT& n , const INT& m );
template <typename INT> inline INT CombinationModularFactorialInverseLoopMethod( const INT& n , const INT& m );
template <typename INT> inline INT Factorial( const INT& n , const INT& n_min , const string& mode ) { return ModularFactorial<INT,INT>( n , n_min , mode ); }
template <typename INT1 , typename INT2> inline INT1 ModularFactorial( const INT2& n , const INT2& n_min , const string& mode ) { return mode == "loop" ? ModularFactorialLoopMethod<INT1,INT2>( n , n_min ) : ModularFactorialNormalMethod<INT1,INT2>( n , n_min ); }
template <typename INT1 , typename INT2>
const INT1& ModularFactorialNormalMethod( const INT2& n )
{
// const参照返しなので静的const変数を返す。
if( n < 1 ){
static const INT1 one = 1;
return one;
}
static VLArray<INT2> memory_n{};
static VLArray<INT1> memory_answer{};
auto itr_n = memory_n.begin() , end_n = memory_n.end();
auto itr_answer = memory_answer.begin();
while( itr_n != end_n ){
if( *itr_n == n ){
return *itr_answer;
}
itr_n++;
itr_answer++;
}
const INT1 answer = n * ModularFactorialNormalMethod<INT1,INT2>( n - 1 );
memory_n.push_front( n );
memory_answer.push_front( answer );
return memory_answer.front();
}
template <typename INT1 , typename INT2>
const INT1& ModularFactorialNormalMethod( const INT2& n , const INT2& n_min )
{
if( n_min == 1 ){
return ModularFactorialNormalMethod<INT1,INT2>( n );
}
return ModularFactorialNormalMethod_Body<INT1,INT2>( n , n_min );
}
template <typename INT1 , typename INT2>
const INT1& ModularFactorialNormalMethod_Body( const INT2& n , const INT2& n_min )
{
// const参照返しなので静的const変数を返す。
if( n < n_min ){
static const INT1 one = 1;
return one;
}
static VLArray<INT2> memory_n{};
static VLArray<VLArray<INT2> > memory_n_min{};
static VLArray<VLArray<INT1> > memory_answer{};
VLArray<INT2>* p_n_min = nullptr;
VLArray<INT1>* p_answer = nullptr;
auto itr_n = memory_n.begin() , end_n = memory_n.end();
auto itr_n_min = memory_n_min.begin();
auto itr_answer = memory_answer.begin();
while( itr_n != end_n && p_n_min == nullptr ){
if( *itr_n == n ){
p_n_min = &( *itr_n_min );
p_answer = &( *itr_answer );
}
itr_n++;
itr_n_min++;
itr_answer++;
}
if( p_n_min == nullptr ){
memory_n.push_front( n );
memory_n_min.push_front( VLArray<INT2>() );
memory_answer.push_front( VLArray<INT1>() );
p_n_min = &( memory_n_min.front() );
p_answer = &( memory_answer.front() );
}
auto itr_n_min_current = p_n_min->begin() , end_n_min_current = p_n_min->end();
auto itr_answer_current = p_answer->begin();
while( itr_n_min_current != end_n_min_current ){
if( *itr_n_min_current == n_min ){
return *itr_answer_current;
}
itr_n_min_current++;
itr_answer_current++;
}
const INT1 answer = ModularFactorialNormalMethod<INT1,INT2>( n , n_min + 1 ) * n_min;
p_n_min->push_front( n_min );
p_answer->push_front( answer );
return p_answer->front();
}
template <typename INT1 , typename INT2>
INT1 ModularFactorialLoopMethod( const INT2& n , const INT2& n_min )
{
INT1 f = 1;
for( INT2 i = n_min ; i <= n ; i++ ){
f *= i;
}
return f;
}
template <typename INT1 , typename INT2> inline INT1 ModularFactorialInverse( const INT2& n , const INT2& n_min , const string& mode ) { return mode == "loop" ? ModularFactorialInverseLoopMethod<INT1,INT2>( n , n_min ) : ModularFactorialInverseNormalMethod<INT1,INT2>( n , n_min ); }
template <typename INT1 , typename INT2>
const INT1& ModularFactorialInverseNormalMethod( const INT2& n )
{
// const参照返しなので静的const変数を返す。
if( n < 1 ){
static const INT1 one = 1;
return one;
}
static VLArray<INT2> memory_n{};
static VLArray<INT1> memory_answer{};
auto itr_n = memory_n.begin() , end_n = memory_n.end();
auto itr_answer = memory_answer.begin();
while( itr_n != end_n ){
if( *itr_n == n ){
return *itr_answer;
}
itr_n++;
itr_answer++;
}
const INT1 answer = ModularFactorialInverseNormalMethod<INT1,INT2>( n - 1 ) / n;
memory_n.push_front( n );
memory_answer.push_front( answer );
return memory_answer.front();
}
template <typename INT1 , typename INT2>
const INT1& ModularFactorialInverseNormalMethod( const INT2& n , const INT2& n_min )
{
if( n_min == 1 ){
return ModularFactorialInverseNormalMethod<INT1,INT2>( n );
}
return ModularFactorialInverseNormalMethod_Body<INT1,INT2>( n , n_min );
}
template <typename INT1 , typename INT2>
const INT1& ModularFactorialInverseNormalMethod_Body( const INT2& n , const INT2& n_min )
{
// const参照返しなので静的const変数を返す。
if( n < n_min ){
static const INT1 one = 1;
return one;
}
static VLArray<INT2> memory_n{};
static VLArray<VLArray<INT2> > memory_n_min{};
static VLArray<VLArray<INT1> > memory_answer{};
VLArray<INT2>* p_n_min = nullptr;
VLArray<INT1>* p_answer = nullptr;
auto itr_n = memory_n.begin() , end_n = memory_n.end();
auto itr_n_min = memory_n_min.begin();
auto itr_answer = memory_answer.begin();
while( itr_n != end_n && p_n_min == nullptr ){
if( *itr_n == n ){
p_n_min = &( *itr_n_min );
p_answer = &( *itr_answer );
}
itr_n++;
itr_n_min++;
itr_answer++;
}
if( p_n_min == nullptr ){
memory_n.push_front( n );
memory_n_min.push_front( VLArray<INT2>() );
memory_answer.push_front( VLArray<INT1>() );
p_n_min = &( memory_n_min.front() );
p_answer = &( memory_answer.front() );
}
auto itr_n_min_current = p_n_min->begin() , end_n_min_current = p_n_min->end();
auto itr_answer_current = p_answer->begin();
while( itr_n_min_current != end_n_min_current ){
if( *itr_n_min_current == n_min ){
return *itr_answer_current;
}
itr_n_min_current++;
itr_answer_current++;
}
const INT1 answer = ModularFactorialInverseNormalMethod<INT1,INT2>( n , n_min + 1 ) / (INT1)n_min;
p_n_min->push_front( n_min );
p_answer->push_front( answer );
return p_answer->front();
}
template <typename INT1 , typename INT2>
INT1 ModularFactorialInverseLoopMethod( const INT2& n , const INT2& n_min )
{
INT1 f = 1;
for( INT2 i = n_min ; i <= n ; i++ ){
f /= i;
}
return f;
}
template <typename INT>
INT Combination( const INT& n , const INT& m , const string& mode )
{
if( n < m ){
return 0;
}
if( mode == "loop" ){
return CombinationLoopMethod<INT>( n , m );
}
if( mode == "factorial normal" ){
return CombinationFactorialNormalMethod<INT>( n , m );
}
if( mode == "factorial loop" ){
return CombinationFactorialLoopMethod<INT>( n , m );
}
if( mode == "modular factorial inverse normal" ){
return CombinationModularFactorialInverseNormalMethod<INT>( n , m );
}
if( mode == "modular factorial inverse loop" ){
return CombinationModularFactorialInverseLoopMethod<INT>( n , m );
}
return CombinationNormalMethod<INT>( n , m );
}
template <typename INT>
const INT& CombinationNormalMethod( const INT& n , const INT& m )
{
// const参照返しなので静的const変数を返す。
if( m == 0 ){
static const INT one = 1;
return one;
}
static VLArray<INT> memory_n{};
static VLArray<VLArray<INT> > memory_m{};
static VLArray<VLArray<INT> > memory_answer{};
VLArray<INT>* p_m = nullptr;
VLArray<INT>* p_answer = nullptr;
auto itr_n = memory_n.begin() , end_n = memory_n.end();
auto itr_m = memory_m.begin();
auto itr_answer = memory_answer.begin();
while( itr_n != end_n && p_m == nullptr ){
if( *itr_n == n ){
p_m = &( *itr_m );
p_answer = &( *itr_answer );
}
itr_n++;
itr_m++;
itr_answer++;
}
if( p_m == nullptr ){
memory_n.push_front( n );
memory_m.push_front( VLArray<INT>() );
memory_answer.push_front( VLArray<INT>() );
p_m = &( memory_m.front() );
p_answer = &( memory_answer.front() );
}
const INT size = p_m->size();
// p_mには{...,3,2,1}と入っていくのでm <= sizeの時にmが見付かる。
if( m <= size ){
auto itr_m_current = p_m->begin() , end_m_current = p_m->end();
auto itr_answer_current = p_answer->begin();
while( itr_m_current != end_m_current ){
if( *itr_m_current == m ){
return *itr_answer_current;
}
itr_m_current++;
itr_answer_current++;
}
}
const INT answer = ( CombinationNormalMethod<INT>( n , m - 1 ) * ( n - m + 1 ) ) / m;
p_m->push_front( m );
p_answer->push_front( answer );
return p_answer->front();
}
template <typename INT>
INT CombinationLoopMethod( const INT& n , const INT& m )
{
const INT m_comp = n - m;
const INT m_copy = m_comp < m ? m_comp : m;
INT answer = 1;
for( INT i = 0 ; i < m_copy ; i++ ){
answer *= ( n - i );
answer /= i + 1;
}
return answer;
}
template <typename INT> inline INT CombinationFactorialNormalMethod( const INT& n , const INT& m ) { return Factorial<INT>( n , n - m + 1 , "normal" ) / Factorial<INT>( m , 1 , "normal" ); }
template <typename INT> inline INT CombinationFactorialLoopMethod( const INT& n , const INT& m ) { return Factorial<INT>( n , n - m + 1 , "loop" ) / Factorial<INT>( m , 1 , "loop" ); }
template <typename INT> inline INT CombinationModularFactorialInverseNormalMethod( const INT& n , const INT& m ) { return Factorial<INT>( n , n - m + 1 , "normal" ) * ModularFactorialInverse<INT,INT>( m , 1 , "normal" ); }
template <typename INT> inline INT CombinationModularFactorialInverseLoopMethod( const INT& n , const INT& m ) { return Factorial<INT>( n , n - m + 1 , "loop" ) * ModularFactorialInverse<INT,INT>( m , 1 , "loop" ); }
constexpr const ll P = 998244353;
int main(){
CIN( ll , N );
CIN( ll , K );
// S = sum_{i=1}^{N} S(i) e_i = sum_{i=1}^{N} S(i) (e_i - e_1)
// = sum_{i=1}^{N} S(i) sum_{j=1}^{i-1} b_j
// = sum_{j=1}^{N} ( ( sum_{i=j+1}^{N} S(i) ) % 2 ) b_j
// f(S) = sum_{j=1}^{N} ( sum_{i=j+1}^{N} S(i) ) % 2
// = Sの1のうち右から数えて奇数番目のものの左に続く0の個数+1の総和
// #{S|f(S) = d} = N個のうち左端以外からd個選ぶ方法の総数 = C( N - 1 , d )
// answer = sum_{d=0}^{N-1} C(N-1,d) d^K;
ll N_minus = N - 1;
const string mode_comb = "normal";
const string mode_pow = "binary";
Mod<P> answer{ 0 };
FOR_LL( d , 0 , N ){
answer += Combination<Mod<P> >( N_minus , d , mode_comb ) * Power<Mod<P>,ll>( Mod<P>( d ) , K , 1 , true , mode_pow );
}
RETURN( answer.Represent() );
}