#824135 (C++17) No.2156 ぞい文字列

提出ソース
結果

問題	No.2156 ぞい文字列
ユーザー	👑 p-adic
提出日時	2022-12-09 22:15:03
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	35,486 bytes
コンパイル時間	4,049 ms
コンパイル使用メモリ	239,656 KB
実行使用メモリ	4,384 KB
最終ジャッジ日時	2023-08-05 00:00:41
合計ジャッジ時間	4,662 ms
ジャッジサーバーID （参考情報）	judge11 / judge13
このコードへのチャレンジ（β）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,380 KB
testcase_01	AC	1 ms 4,376 KB
testcase_02	AC	2 ms 4,380 KB
testcase_03	AC	2 ms 4,376 KB
testcase_04	AC	2 ms 4,376 KB
testcase_05	AC	1 ms 4,376 KB
testcase_06	AC	2 ms 4,380 KB
testcase_07	AC	2 ms 4,376 KB
testcase_08	AC	2 ms 4,380 KB
testcase_09	AC	2 ms 4,380 KB
testcase_10	AC	1 ms 4,380 KB
testcase_11	AC	1 ms 4,380 KB
testcase_12	AC	2 ms 4,380 KB
testcase_13	AC	1 ms 4,376 KB
testcase_14	AC	1 ms 4,376 KB
testcase_15	AC	1 ms 4,384 KB
testcase_16	AC	2 ms 4,376 KB
testcase_17	AC	2 ms 4,380 KB
testcase_18	AC	1 ms 4,376 KB
testcase_19	AC	1 ms 4,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#pragma GCC optimize ( "O3" )
#pragma GCC target ( "avx" )
#include <bits/stdc++.h>
using namespace std;

using uint = unsigned int;
using ll = long long;

#define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) 
#define CEXPR( LL , BOUND , VALUE ) constexpr const LL BOUND = VALUE 
#define CIN( LL , A ) LL A; cin >> A 
#define ASSERT( A , MIN , MAX ) assert( MIN <= A && A <= MAX ) 
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX ) 
#define GETLINE( A ) string A; getline( cin , A ) 
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR ) 
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) 
#define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) 
#define FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; VAR -- ) 
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ ) 
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) 
#define QUIT return 0 
#define COUT( ANSWER ) cout << ( ANSWER ) << "\n"; 
#define RETURN( ANSWER ) COUT( ANSWER ); QUIT 
#define DOUBLE( PRECISION , ANSWER ) cout << fixed << setprecision( PRECISION ) << ( ANSWER ) << "\n"; QUIT 

#define POWER( ANSWER , ARGUMENT , EXPONENT )				\
  TYPE_OF( ARGUMENT ) ANSWER{ 1 };					\
  {									\
    TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT );	\
    TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT );	\
    while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){			\
      if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){			\
	ANSWER *= ARGUMENT_FOR_SQUARE_FOR_POWER;			\
      }									\
      ARGUMENT_FOR_SQUARE_FOR_POWER *= ARGUMENT_FOR_SQUARE_FOR_POWER;	\
      EXPONENT_FOR_SQUARE_FOR_POWER /= 2;				\
    }									\
  }									\


#define POWER_MOD( ANSWER , ARGUMENT , EXPONENT , MODULO )		\
  TYPE_OF( ARGUMENT ) ANSWER{ 1 };					\
  {									\
    TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( MODULO + ( ARGUMENT ) % MODULO ) % MODULO; \
    TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT );	\
    while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){			\
      if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){			\
	ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO;	\
      }									\
      ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \
      EXPONENT_FOR_SQUARE_FOR_POWER /= 2;				\
    }									\
  }									\


#define FACTORIAL_MOD( ANSWER , ANSWER_INV , MAX_I , LENGTH , MODULO )	\
  ll ANSWER[LENGTH];							\
  ll ANSWER_INV[LENGTH];						\
  {									\
    ll VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1;				\
    ANSWER[0] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL;			\
    FOREQ( i , 1 , MAX_I ){						\
      ANSWER[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= i ) %= MODULO; \
    }									\
    POWER_MOD( FACTORIAL_MAX_INV , ANSWER[MAX_I] , MODULO - 2 , MODULO ); \
    ANSWER_INV[MAX_I] = FACTORIAL_MAX_INV;				\
    FOREQINV( i , MAX_I - 1 , 0 ){					\
      ANSWER_INV[i] = ( FACTORIAL_MAX_INV *= i + 1 ) %= MODULO;		\
    }									\
  }									\
									\


// 通常の二分探索
#define BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET )		\
  ll ANSWER = MAXIMUM;							\
  {									\
    ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM;				\
    ll VARIABLE_FOR_BINARY_SEARCH_U = ANSWER;				\
    ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \
    if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){		\
      VARIABLE_FOR_BINARY_SEARCH_L = ANSWER;				\
    } else {								\
      ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
    }									\
    while( VARIABLE_FOR_BINARY_SEARCH_L != ANSWER ){			\
      VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \
      if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){		\
	VARIABLE_FOR_BINARY_SEARCH_L = ANSWER;				\
	break;								\
      } else {								\
	if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){		\
	  VARIABLE_FOR_BINARY_SEARCH_L = ANSWER;			\
	} else {							\
	  VARIABLE_FOR_BINARY_SEARCH_U = ANSWER;			\
	}								\
	ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
      }									\
    }									\
  }									\
									\


// 二進法の二分探索
#define BS2( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET )		\
  ll ANSWER = MINIMUM;							\
  {									\
    ll VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 = 1;			\
    ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( MAXIMUM ) - ANSWER; \
    while( VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 <= VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ){ \
      VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 *= 2;			\
    }									\
    VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 /= 2;			\
    ll VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER;		\
    while( VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 != 0 ){		\
      ANSWER = VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 + VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2; \
      VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \
      if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){		\
	VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER;		\
	break;								\
      } else if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){	\
	VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER;		\
      }									\
      VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 /= 2;			\
    }									\
    ANSWER = VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2;			\
  }									\
									\


template <typename T> inline T Absolute( const T& a ){ return a > 0 ? a : - a; }
// template <typename T> inline T Residue( const T& a , const T& p ){ return a >= 0 ? a % p : p - ( - a - 1 ) % p - 1; }





template <typename T>
using VLArray = list<T>;

// template <typename T>
// using LineTypeForMatrix = VLArray<T>;
// vectorの方が乗法の計算が高速
template <typename T>
using LineTypeForMatrix = vector<T>;

template <typename T>
using TableTypeForMatrix = LineTypeForMatrix<LineTypeForMatrix<T> >;

// using SizeTypeForMatrix = uint;
using SizeTypeForMatrix = ll;


template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
class Matrix
{

private:
  TableTypeForMatrix<T>  m_M;

public:
  // argsの長さがXYでなくてもコンパイルエラーとならないがサポート外である。
  template <typename... Args> Matrix( const Args&... args ) noexcept;

  inline Matrix( const Matrix<Y,X,T>& mat ) noexcept;

  // ( X , Y )行列でないものも引数に取れるがサポート外である。
  template <typename... Args> inline Matrix( const TableTypeForMatrix<T>& M ) noexcept;

  Matrix<Y,X,T>& operator=( const Matrix<Y,X,T>& mat ) noexcept;
  Matrix<Y,X,T>& operator+=( const Matrix<Y,X,T>& mat );
  Matrix<Y,X,T>& operator-=( const Matrix<Y,X,T>& mat );
  Matrix<Y,X,T>& operator*=( const T& scalar ) noexcept;

  // 行や列の長さを変更可能だがサポート外である。
  inline TableTypeForMatrix<T>& RefTable() noexcept;
  inline const TableTypeForMatrix<T>& GetTable() const noexcept;

  static inline const Matrix<Y,X,T>& Unit() noexcept;

private:
  static inline void ConstructTable( TableTypeForMatrix<T>& M , LineTypeForMatrix<T>& vec ) noexcept;
  template <typename Arg , typename... Args> static void ConstructTable( TableTypeForMatrix<T>& M , LineTypeForMatrix<T>& vec , const Arg& arg , const Args&... args ) noexcept;
  
  static Matrix<Y,X,T> Unit_Body() noexcept;

};

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> inline Matrix<Y,X,T> operator==( const Matrix<Y,X,T>& mat1 , const Matrix<Y,X,T>& mat2 ) noexcept;

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> inline Matrix<Y,X,T> operator!=( const Matrix<Y,X,T>& mat1 , const Matrix<Y,X,T>& mat2 ) noexcept;

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<Y,X,T> operator+( const Matrix<Y,X,T>& mat1 , const Matrix<Y,X,T>& mat2 );

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<Y,X,T> operator-( const Matrix<Y,X,T>& mat1 , const Matrix<Y,X,T>& mat2 );

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , SizeTypeForMatrix Z , typename T>
Matrix<Y,Z,T> operator*( const Matrix<Y,X,T>& mat1 , const Matrix<X,Z,T>& mat2 );

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<Y,X,T> operator*( const T& scalar , const Matrix<Y,X,T>& mat );

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<X,Y,T> Transpose( const Matrix<Y,X,T>& mat );

template <SizeTypeForMatrix X , typename T>
T Trace( const Matrix<X,X,T>& mat );


// ../Arithmetic/Power/a_Body.hppにて定義
// template <typename T , typename UINT>
// T PowerBinaryMethod( const T& t , const UINT& num , const T& init , const bool& for_right_multiplication );
// template <typename T , typename UINT>
// Matrix<2,2,T> PowerBinaryMethod( const Matrix<2,2,T>& mat , const UINT& num , const Matrix<2,2,T>& init_dummy , const bool& for_right_multiplication_dummy );


template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> template <typename... Args>
Matrix<Y,X,T>::Matrix( const Args&... args ) noexcept
  : m_M()
{

  TableTypeForMatrix<T> M{};
  LineTypeForMatrix<T> vec{};
  ConstructTable( M , vec , args... );
  m_M = M;

}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> inline Matrix<Y,X,T>::Matrix( const Matrix<Y,X,T>& mat ) noexcept : m_M( mat.m_M ) {}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> template <typename... Args> inline Matrix<Y,X,T>::Matrix( const TableTypeForMatrix<T>& M ) noexcept : m_M( M ) {}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<Y,X,T>& Matrix<Y,X,T>::operator=( const Matrix<Y,X,T>& mat ) noexcept
{

  m_M = mat.m_M;
  return *this;

}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<Y,X,T>& Matrix<Y,X,T>::operator+=( const Matrix<Y,X,T>& mat )
{

  auto itr1y = m_M.begin() , end1y = m_M.end();
  auto itr2y = mat.m_M.begin();  

  while( itr1y != end1y ){

    auto itr1xy = itr1y->begin() , end1xy = itr1y->end();
    auto itr2xy = itr2y->begin();  

    while( itr1xy != end1xy ){

      *itr1xy += *itr2xy;
      itr1xy++;
      itr2xy++;

    }
    
    itr1y++;
    itr2y++;

  }
  
  return *this;

}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<Y,X,T>& Matrix<Y,X,T>::operator-=( const Matrix<Y,X,T>& mat )
{

  auto itr1y = m_M.begin() , end1y = m_M.end();
  auto itr2y = mat.m_M.begin();  

  while( itr1y != end1y ){

    auto itr1xy = itr1y->begin() , end1xy = itr1y->end();
    auto itr2xy = itr2y->begin();  

    while( itr1xy != end1xy ){

      *itr1xy -= *itr2xy;
      itr1xy++;
      itr2xy++;

    }
    
    itr1y++;
    itr2y++;

  }
  
  return *this;

}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> Matrix<Y,X,T>& Matrix<Y,X,T>::operator*=( const T& scalar ) noexcept
{

  for( auto itry = m_M.begin() , endy = m_M.end() ; itry != endy ; itry++ ){

    for( auto itrxy = itry->begin() , endxy = itry->end() ; itrxy != endxy ; itrxy++ ){

      *itrxy *= scalar;

    }

  }

  return *this;

}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> inline TableTypeForMatrix<T>& Matrix<Y,X,T>::RefTable() noexcept { return m_M; }
template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> inline const TableTypeForMatrix<T>& Matrix<Y,X,T>::GetTable() const noexcept { return m_M; }

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> inline const Matrix<Y,X,T>& Matrix<Y,X,T>::Unit() noexcept { static const Matrix<Y,X,T> unit = Unit_Body(); return unit; }

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<Y,X,T> Matrix<Y,X,T>::Unit_Body() noexcept
{

  TableTypeForMatrix<T> M{};
  
  for( SizeTypeForMatrix y = 0 ; y < Y ; y++ ){

    LineTypeForMatrix<T> vec{};

    for( SizeTypeForMatrix x = 0 ; x < X ; x++ ){

      vec.push_back( x == y ? 1 : 0 );

    }

    M.push_back( vec );

  }

  return Matrix<Y,X,T>( M );

}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> inline void Matrix<Y,X,T>::ConstructTable( TableTypeForMatrix<T>& M , LineTypeForMatrix<T>& vec ) noexcept { M.push_back( vec ); vec.clear(); }

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> template <typename Arg , typename... Args> void Matrix<Y,X,T>::ConstructTable( TableTypeForMatrix<T>& M , LineTypeForMatrix<T>& vec , const Arg& arg , const Args&... args ) noexcept
{

  vec.push_back( arg );

  if( vec.size() == X ){

    ConstructTable( M , vec );

  }

  if( M.size() < Y ){

    ConstructTable( M , vec , args... );

  }
  
  return;

}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> inline Matrix<Y,X,T> operator==( const Matrix<Y,X,T>& mat1 , const Matrix<Y,X,T>& mat2 ) noexcept { return mat1.GetTable() == mat2.GetTable(); }

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> inline Matrix<Y,X,T> operator!=( const Matrix<Y,X,T>& mat1 , const Matrix<Y,X,T>& mat2 ) noexcept { return !( mat1 == mat2 ); }

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<Y,X,T> operator+( const Matrix<Y,X,T>& mat1 , const Matrix<Y,X,T>& mat2 )
{

  Matrix<Y,X,T> mat1_copy = mat1;
  mat1_copy += mat2;
  return mat1_copy;

}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<Y,X,T> operator-( const Matrix<Y,X,T>& mat1 , const Matrix<Y,X,T>& mat2 )
{

  Matrix<Y,X,T> mat1_copy = mat1;
  mat1_copy -= mat2;
  return mat1_copy;

}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , SizeTypeForMatrix Z , typename T> inline Matrix<Y,Z,T> operator*( const Matrix<Y,X,T>& mat1 , const Matrix<X,Z,T>& mat2 )
{

  const TableTypeForMatrix<T>& M1 = mat1.GetTable();
  const TableTypeForMatrix<T>& M2 = mat2.GetTable();
  TableTypeForMatrix<T> M_prod{};
  auto begin2x = M2.begin();
  
  for( auto itr1y = M1.begin() , end1y = M1.end() ; itr1y != end1y ; itr1y++ ){

    LineTypeForMatrix<T> vec{};
    auto begin1yx = itr1y->begin() , end1yx = itr1y->end();

    for( SizeTypeForMatrix z = 0 ; z < Z ; z++ ){

      auto itr1yx = begin1yx;
      auto itr2x = begin2x;

      T inner_product = 0;
      
      while( itr1yx != end1yx ){

	inner_product += ( *itr1yx ) * ( *itr2x )[z];
	itr1yx++;
	itr2x++;

      }

      vec.push_back( inner_product );

    }

    M_prod.push_back( vec );

  }

  return Matrix<Y,Z,T>( M_prod );

}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<Y,X,T> operator*( const T& scalar , const Matrix<Y,X,T>& mat )
{

  Matrix<Y,X,T> mat_copy = mat;
  mat_copy *= scalar;
  return mat_copy;

}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<X,Y,T> Transpose( const Matrix<Y,X,T>& mat )
{

  const TableTypeForMatrix<T>& M = mat.GetTable();
  TableTypeForMatrix<T> M_t{};

  auto beginy = M.begin();

  for( auto itr1x = beginy->begin() , end1x = beginy->end() ; itr1x != end1x ; itr1x++ ){

    M_t.push_back( LineTypeForMatrix<T>() );

  }

  for( auto itry = beginy , endy = M.end() ; itry != endy ; itry++ ){

    auto itryx = itry->begin() , endyx = itry->end();
    auto itr_ty = M_t.begin();

    while( itryx != endyx ){

      itr_ty->push_back( *itryx );
      itryx++;
      itr_ty++;

    }

  }

  return Matrix<X,Y,T>( M_t );

}

template <SizeTypeForMatrix X , typename T>
T Trace( const Matrix<X,X,T>& mat )
{

  int i = 0;
  T answer =0;
  const TableTypeForMatrix<T>& M = mat.GetTable();

  for( auto itry = M.begin() , endy = M.end() ; itry != endy ; itry++ ){

    answer += ( *itry )[i];
    i++;

  }

  return answer;

}

// template <typename T , typename UINT> inline Matrix<2,2,T> PowerBinaryMethod( const Matrix<2,2,T>& mat , const UINT& num , const Matrix<2,2,T>& init_dummy , const bool& for_right_multiplication_dummy ) { return PowerBinaryMethod( TwoByTwoMatrix<T>( mat ) , num , TwoByTwoMatrix<T>( init_dummy ) , for_right_multiplication_dummy ).GetMatrix22(); }

// using INT_TYPE_FOR_MOD = int;
using INT_TYPE_FOR_MOD = long long int;


void LazyEvaluationOfModularInverse( const INT_TYPE_FOR_MOD& M , const INT_TYPE_FOR_MOD& n , INT_TYPE_FOR_MOD& m );



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;

}


// ここを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-() const noexcept;

  // 前置++/--を使うつもりがないので後置++/--と同じものとして定義する
  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 );

template <INT_TYPE_FOR_MOD M> inline string to_string( const Mod<M>& n ) noexcept;

template<INT_TYPE_FOR_MOD M , class Traits> inline basic_ostream<char,Traits>& operator<<( basic_ostream<char,Traits>& os , const Mod<M>& n );



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;

}


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-() const noexcept { return Mod<M>( 0 ).operator-=( *this ); }

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; }

template <INT_TYPE_FOR_MOD M> inline string to_string( const Mod<M>& n ) noexcept { return to_string( n.Represent() ) + " + MZ"; }

template<INT_TYPE_FOR_MOD M , class Traits> inline basic_ostream<char,Traits>& operator<<( basic_ostream<char,Traits>& os , const Mod<M>& n ) { return os << n.Represent(); }


int main()
{
  UNTIE;
  CEXPR( ll , bound_N , 1000000000000000000 );
  CIN_ASSERT( N , 2 , bound_N );
  // A[2] = 1;
  // A[n] = 1 + sum( int i = 2 ; i <= n - 2 ; i++ ) A[i];
  // A[3] = 1;
  // A[4] = 2;
  // A[5] = 3;
  // A[6] = 5;
  using MOD = Mod<998244353>;
  Matrix<2,1,MOD> v
  {
    1 ,
      1
  };
  Matrix<2,2,MOD> T
  {
    1 , 1 ,
      1 , 0
  };
  Matrix<2,2,MOD> power_T = Matrix<2,2,MOD>::Unit();
  Matrix<2,2,MOD> power{ T };
  N -= 2;
  while( N != 0 ){
    if( N % 2 == 1 ){
      power_T = power_T * power;
    }
    power = power * power;
    N /= 2;
  }
  v = power_T * v;
  const TableTypeForMatrix<MOD>& v_vec = v.GetTable();
  RETURN( ( v_vec[0][0] + v_vec[1][0] - 1 ).Represent() );
}
yukicoder

結果

テストケース

ソースコード
