#829713 (C++17(gcc12)) No.2130 分配方法の数え上げ mod 998244353

提出ソース
結果

問題	No.2130 分配方法の数え上げ mod 998244353
コンテスト
ユーザー	👑 p-adic
提出日時	2023-01-01 19:01:41
言語	C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
結果	AC
実行時間	5 ms / 2,000 ms
コード長	16,526 bytes
コンパイル時間	1,789 ms
コンパイル使用メモリ	194,904 KB
最終ジャッジ日時	2025-02-09 22:44:30
ジャッジサーバーID （参考情報）	judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 38
権限があれば一括ダウンロードができます
ソースコード

raw source code
// 手持ちのMod<998244353>のライブラリがバグってしまったのでデバッグ用提出。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define TYPE_OF( VAR ) decay_t<decltype( VAR )>
#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 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 COUT( ANSWER ) cout << ( ANSWER ) << "\n";
#define QUIT return 0 
#define RETURN( ANSWER ) COUT( ANSWER ); QUIT 

#define POWER( ANSWER , VAR , EXPONENT_REF , MODULO )			\
  TYPE_OF( VAR ) ANSWER = 1;						\
  TYPE_OF( VAR ) VARIABLE_FOR_SQUARE_FOR_POWER = VAR;			\
  while( EXPONENT_REF != 0 ){						\
    if( EXPONENT_REF % 2 == 1 ){					\
      ANSWER = ( ANSWER * VARIABLE_FOR_SQUARE_FOR_POWER ) % MODULO;	\
    }									\
    VARIABLE_FOR_SQUARE_FOR_POWER = ( VARIABLE_FOR_SQUARE_FOR_POWER * VARIABLE_FOR_SQUARE_FOR_POWER ) % MODULO;	\
    EXPONENT_REF /= 2;							\
  }			

template <typename INT1 , typename INT2> inline INT1& Residue( INT1& n , const INT2& M ) noexcept { return n >= 0 ? n %= M : ( ( ( ( ++n ) *= -1 ) %= M ) *= -1 ) += M - 1; }
template <typename INT1 , typename INT2> inline INT1 Residue( INT1&& n , const INT2& M ) noexcept { return move( Residue( n , M ) ); }
template <typename INT1 , typename INT2> inline INT1 Residue( const INT1& n , const INT2& M ) noexcept { return Residue( move( INT1( n ) ) , M ); }

#define SFINAE_TYPE_FOR_MOD( TYPE )			\
  decltype( INT_TYPE_FOR_MOD( decay_t<T>() ) , TYPE() )	\

#define DECLARATION_OF_COMPARISON_FOR_MOD( FUNC )	\
  inline bool operator FUNC( const Mod<M>& n ) const noexcept	\

#define DECLARATION_OF_ARITHMETIC_FOR_MOD( FUNC )			\
  inline Mod<M> operator FUNC( const Mod<M>& n ) const noexcept;			\
  template <typename T> inline SFINAE_TYPE_FOR_MOD( Mod<M> ) operator FUNC( T&& n ) const noexcept; \

#define DEFINITION_OF_COMPARISON_FOR_MOD( FUNC )			\
  template <INT_TYPE_FOR_MOD M> inline bool Mod<M>::operator FUNC( const Mod<M>& n ) const noexcept { return m_n FUNC n.m_n; } \

#define DEFINITION_OF_ARITHMETIC_FOR_MOD( FUNC , FORMULA )		\
  template <INT_TYPE_FOR_MOD M> inline Mod<M> Mod<M>::operator FUNC( const Mod<M>& n ) const noexcept { return move( Mod<M>( *this ) FUNC ## = n ); } \
  template <INT_TYPE_FOR_MOD M> template <typename T> inline SFINAE_TYPE_FOR_MOD( Mod<M> ) Mod<M>::operator FUNC( T&& n ) const noexcept { return FORMULA; } \
  template <INT_TYPE_FOR_MOD M , typename T> inline SFINAE_TYPE_FOR_MOD( Mod<M> ) operator FUNC( T&& n0 , const Mod<M>& n1 ) noexcept { return move( Mod<M>( forward<T>( n0 ) ) FUNC ## = n1 ); } \

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

using INT_TYPE_FOR_MOD = int;
// using INT_TYPE_FOR_MOD = ll;

// ここを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;

public:
  inline Mod() noexcept;
  inline Mod( const Mod<M>& n ) noexcept;
  inline Mod( Mod<M>& n ) noexcept;
  // INT_TYPE_FOR_MODがintならば恐らく実行速度に影響しないが念のため。
  inline Mod( Mod<M>&& n ) noexcept;
  template <typename T> inline Mod( T& n , SFINAE_TYPE_FOR_MOD( int ) dummy = 0 ) noexcept;
  template <typename T> inline Mod( T&& n , SFINAE_TYPE_FOR_MOD( int ) dummy = 0 ) noexcept;
  
  inline Mod<M>& operator=( const Mod<M>& n ) noexcept;
  inline Mod<M>& operator+=( const Mod<M>& n ) noexcept;
  inline Mod<M>& operator-=( const Mod<M>& n ) noexcept;
  inline Mod<M>& operator*=( const Mod<M>& n ) noexcept;
  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;

  DECLARATION_OF_COMPARISON_FOR_MOD( == );
  DECLARATION_OF_COMPARISON_FOR_MOD( != );
  DECLARATION_OF_COMPARISON_FOR_MOD( < );
  DECLARATION_OF_COMPARISON_FOR_MOD( <= );
  DECLARATION_OF_COMPARISON_FOR_MOD( > );
  DECLARATION_OF_COMPARISON_FOR_MOD( >= );

  DECLARATION_OF_ARITHMETIC_FOR_MOD( + );
  DECLARATION_OF_ARITHMETIC_FOR_MOD( - );
  DECLARATION_OF_ARITHMETIC_FOR_MOD( * );
  DECLARATION_OF_ARITHMETIC_FOR_MOD( / );

  inline Mod<M> operator-() const noexcept;
  inline Mod<M>& SignInvert() noexcept;
  // Mが素数である場合のみサポート。
  inline Mod<M>& Invert();
  template <typename T> inline Mod<M>& PositivePower( T&& exponent ) noexcept;
  // Mが素数であるかexponent>=0である場合にのみサポート。
  template <typename T> inline Mod<M>& Power( T&& exponent );
  
  inline const INT_TYPE_FOR_MOD& Represent() const noexcept;
  inline void swap( Mod<M>& n ) noexcept;

  // Mが素数かつn < g_memory_lengthである場合のみサポート。
  static inline const INT_TYPE_FOR_MOD& Inverse( const INT_TYPE_FOR_MOD& n ) noexcept;
  // n < g_memory_lengthである場合のみサポート。
  static inline const INT_TYPE_FOR_MOD& Factorial( const INT_TYPE_FOR_MOD& n ) noexcept;
  // Mが素数かつn < g_memory_lengthである場合のみサポート。
  static inline const INT_TYPE_FOR_MOD& FactorialInverse( const INT_TYPE_FOR_MOD& n ) noexcept;

  static inline const Mod<M>& zero() noexcept;
  static inline const Mod<M>& one() noexcept;

private:
  static inline constexpr int BinaryDigitUpperBound() noexcept;
  static inline constexpr ll MontgomeryBasePower( INT_TYPE_FOR_MOD&& exponent ) noexcept;
  static constexpr const int g_Montgomery_digit = BinaryDigitUpperBound();
  static constexpr const ll g_Montgomery_base = ll( 1 ) << g_Montgomery_digit;
  static constexpr const ll g_Montgomery_base_minus = g_Montgomery_base - 1;
  static constexpr const ll g_Montgomery_M_negative_inverse = g_Montgomery_base - MontgomeryBasePower( ( 1 << ( g_Montgomery_digit - 1 ) ) - 1 );
  static constexpr const ll g_Montgomery_base_square = ( g_Montgomery_base * g_Montgomery_base ) % M;
  static constexpr const INT_TYPE_FOR_MOD g_memory_bound = 1000000;
  static constexpr const INT_TYPE_FOR_MOD g_memory_length = M < g_memory_bound ? M : g_memory_bound;
  static inline ll MontgomeryTranformation( const INT_TYPE_FOR_MOD& n ) noexcept;
  static inline ll& MontgomeryReduction( ll& n ) noexcept;
  static inline INT_TYPE_FOR_MOD MontgomeryMultiplication( const INT_TYPE_FOR_MOD& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept;
  static inline void Normalise( INT_TYPE_FOR_MOD& n ) noexcept;

};

// Mが素数である場合にのみサポート。
template <INT_TYPE_FOR_MOD M> Mod<M> inline Inverse( const Mod<M>& n );

// Mが素数であるかexponent>=0である場合にのみサポート。
template <INT_TYPE_FOR_MOD M , typename T> inline Mod<M> Power( const Mod<M>& n , const T& exponent );
template <typename T> inline Mod<2> Power( const Mod<2>& n , const T& p );

// ../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 void swap( Mod<M>& n0 , Mod<M>& n1 ) noexcept;

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 <INT_TYPE_FOR_MOD M> inline constexpr int Mod<M>::BinaryDigitUpperBound() noexcept { int answer = 0; ll power = 1; while( M > power ){ answer++; power <<= 1; } return answer; }
template <INT_TYPE_FOR_MOD M> inline constexpr ll Mod<M>::MontgomeryBasePower( INT_TYPE_FOR_MOD&& exponent ) noexcept { ll prod = 1; ll power = M; while( exponent != 0 ){ if( ( exponent & 1 ) == 1 ){ ( prod *= power ) &= g_Montgomery_base_minus; } ( power *= power ) &= g_Montgomery_base_minus; exponent >>= 1; } return prod; }
template <INT_TYPE_FOR_MOD M> inline ll Mod<M>::MontgomeryTranformation( const INT_TYPE_FOR_MOD& n ) noexcept { ll n_copy = n; return move( MontgomeryReduction( n_copy *= g_Montgomery_base_square ) ); }
template <INT_TYPE_FOR_MOD M> inline ll& Mod<M>::MontgomeryReduction( ll& n ) noexcept { ll n_copy = n; return ( ( n += ( ( ( n_copy &= g_Montgomery_base_minus ) *= g_Montgomery_M_negative_inverse ) &= g_Montgomery_base_minus ) *= M ) >>= g_Montgomery_digit ) < M ? n : n -= M; }
template <INT_TYPE_FOR_MOD M> inline INT_TYPE_FOR_MOD Mod<M>::MontgomeryMultiplication( const INT_TYPE_FOR_MOD& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { ll n0_copy = n0; return MontgomeryReduction( MontgomeryReduction( n0_copy *= n1 ) *= g_Montgomery_base_square ); }
template <INT_TYPE_FOR_MOD M> inline void Mod<M>::Normalise( INT_TYPE_FOR_MOD& n ) noexcept { if( n >= M ){ n -= M; } else if( n < 0 ){ n += M; } }


template <INT_TYPE_FOR_MOD M> inline Mod<M>::Mod() noexcept : m_n() {}
template <INT_TYPE_FOR_MOD M> inline Mod<M>::Mod( const Mod<M>& n ) noexcept : m_n( n.m_n ) {}
template <INT_TYPE_FOR_MOD M> inline Mod<M>::Mod( Mod<M>& n ) noexcept : m_n( n.m_n ) {}
template <INT_TYPE_FOR_MOD M> inline Mod<M>::Mod( Mod<M>&& n ) noexcept : m_n( move( n.m_n ) ) {}
// nの書き換えを防ぐために明示的にキャスト
template <INT_TYPE_FOR_MOD M> template<typename T> inline Mod<M>::Mod( T& n , SFINAE_TYPE_FOR_MOD( int ) dummy ) noexcept : m_n( Residue( decay_t<T>( n ) , M ) ) {}
template <INT_TYPE_FOR_MOD M> template<typename T> inline Mod<M>::Mod( T&& n , SFINAE_TYPE_FOR_MOD( int ) dummy ) noexcept : m_n( Residue( forward<T>( n ) , M ) ) {}

template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator=( const Mod<M>& n ) noexcept { m_n = n.m_n; return *this; }

template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator+=( const Mod<M>& n ) noexcept { Normalise( m_n += n.m_n ); return *this; }
template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator-=( const Mod<M>& n ) noexcept { Normalise( m_n -= n.m_n ); return *this; }
template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator*=( const Mod<M>& n ) noexcept { m_n = MontgomeryMultiplication( m_n , n.m_n ); return *this; }
template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator/=( const Mod<M>& n ) { return operator*=( Mod<M>( n ).Invert() ); }

template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator++() noexcept { return operator+=( one() ); }
template <INT_TYPE_FOR_MOD M> inline Mod<M> Mod<M>::operator++( int ) noexcept { Mod<M> n{ *this }; operator++(); return n; }
template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator--() noexcept { return operator-=( one() ); }
template <INT_TYPE_FOR_MOD M> inline Mod<M> Mod<M>::operator--( int ) noexcept { Mod<M> n{ *this }; operator--(); return n; }

DEFINITION_OF_COMPARISON_FOR_MOD( == );
DEFINITION_OF_COMPARISON_FOR_MOD( != );
DEFINITION_OF_COMPARISON_FOR_MOD( > );
DEFINITION_OF_COMPARISON_FOR_MOD( >= );
DEFINITION_OF_COMPARISON_FOR_MOD( < );
DEFINITION_OF_COMPARISON_FOR_MOD( <= );

DEFINITION_OF_ARITHMETIC_FOR_MOD( + , Mod<M>( forward<T>( n ) ) += *this );
DEFINITION_OF_ARITHMETIC_FOR_MOD( - , Mod<M>( forward<T>( n ) ).SignInvert() += *this );
DEFINITION_OF_ARITHMETIC_FOR_MOD( * , Mod<M>( forward<T>( n ) ) *= *this );
DEFINITION_OF_ARITHMETIC_FOR_MOD( / , Mod<M>( forward<T>( n ) ).Invert() *= *this );

template <INT_TYPE_FOR_MOD M> inline Mod<M> Mod<M>::operator-() const noexcept { return move( Mod<M>( *this ).SignInvert() ); }
template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::SignInvert() noexcept { if( m_n > 0 ){ m_n = M - m_n; } return *this; }


template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::Invert() { assert( m_n > 0 ); if( m_n < g_memory_length ){ m_n = Inverse( m_n ); } else{ const INT_TYPE_FOR_MOD m_n_minus = M - m_n; if( m_n_minus < g_memory_length ){ m_n = M - Inverse( m_n_minus ); } else { return PositivePower( M - 2 ); } } return *this; }

template <INT_TYPE_FOR_MOD M> template <typename T> inline Mod<M>& Mod<M>::PositivePower( T&& exponent ) noexcept { ll prod = g_Montgomery_base; ll power = MontgomeryTranformation( m_n ); while( exponent != 0 ){ if( ( exponent & 1 ) == 1 ){ MontgomeryReduction( prod *= power ); } MontgomeryReduction( power *= power ); exponent >>= 1; } m_n = INT_TYPE_FOR_MOD( MontgomeryReduction( prod ) ); return *this; }

template <INT_TYPE_FOR_MOD M> template <typename T> inline Mod<M>& Mod<M>::Power( T&& exponent ) { if( exponent < 0 ){ assert( m_n != 0 ); exponent *= 2 - M; } exponent %= M - 1; if( exponent != 0 ){ return PositivePower( forward<T>( exponent ) ); } return *this; }

template <INT_TYPE_FOR_MOD M> inline const INT_TYPE_FOR_MOD& Mod<M>::Inverse( const INT_TYPE_FOR_MOD& n ) noexcept { static INT_TYPE_FOR_MOD memory[g_memory_length] = { -1 , 1 }; static int length_curr = 2; while( length_curr <= n ){ memory[length_curr] = M - MontgomeryMultiplication( memory[M % length_curr] , M / length_curr ); length_curr++; } return memory[n]; }
template <INT_TYPE_FOR_MOD M> inline const INT_TYPE_FOR_MOD& Mod<M>::Factorial( const INT_TYPE_FOR_MOD& n ) noexcept { static INT_TYPE_FOR_MOD memory[g_memory_length] = { 1 , 1 }; static int length_curr = 2; static ll val_curr = g_Montgomery_base; while( length_curr <= n ){ memory[length_curr] = INT_TYPE_FOR_MOD( MontgomeryReduction( val_curr *= MontgomeryTranformation( length_curr ) ) ); length_curr++; } return memory[n]; }
template <INT_TYPE_FOR_MOD M> inline const INT_TYPE_FOR_MOD& Mod<M>::FactorialInverse( const INT_TYPE_FOR_MOD& n ) noexcept { static INT_TYPE_FOR_MOD memory[g_memory_length] = { 1 , 1 }; static int length_curr = 2; static ll val_curr = g_Montgomery_base; while( length_curr <= n ){ memory[length_curr] = INT_TYPE_FOR_MOD( MontgomeryReduction( val_curr *= MontgomeryTranformation( Inverse( length_curr ) ) ) ); length_curr++; } return memory[n]; }

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> inline void Mod<M>::swap( Mod<M>& n ) noexcept { std::swap( m_n , n.m_n ); }

template <INT_TYPE_FOR_MOD M> inline const Mod<M>& Mod<M>::zero() noexcept { static const Mod<M> z{}; return z; }
template <INT_TYPE_FOR_MOD M> inline const Mod<M>& Mod<M>::one() noexcept { static const Mod<M> o{ 1 }; return o; }

template <INT_TYPE_FOR_MOD M> inline Mod<M> Inverse( const Mod<M>& n ) { return move( Mod<M>( n ).Invert() ); }

template <INT_TYPE_FOR_MOD M , typename T> inline Mod<M> Power( const Mod<M>& n , const T& exponent ) { return move( Mod<M>( n ).Power( T( exponent ) ) ); }
template <typename T> inline Mod<2> Power( const Mod<2>& n , const T& exponent ) { return exponent == 0 ? Mod<2>::one() : n; }

template <> inline Mod<2> Square<Mod<2> >( const Mod<2>& t ) { return t; }

template <INT_TYPE_FOR_MOD M> inline void swap( Mod<M>& n0 , Mod<M>& n1 ) noexcept { n0.swap( n1 ); }

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


// 以下は
// https://yukicoder.me/submissions/803764
// のmain関数に上のライブラリを適用したもの。

int main()
{
  constexpr const ll bound_N = 1000000000000000000;
  CIN( ll , N );
  assert( 1 <= N && N <= bound_N );
  constexpr const int bound_M = 100000;
  CIN( int , M );
  assert( 1 <= M && M <= bound_M );
  if( N < M ){
    RETURN( 0 );
  }
  constexpr const ll P = 998244353;
  Mod<P> answer{ 2 };
  ll N_copy = N % ( P - 1 );
  answer.PositivePower( N_copy );
  Mod<P> combination{ N };
  answer--;
  if( M != 1 ){
    answer -= N;
  }
  FOR( i , 2 , M ){
    combination *= N + 1 - i;
    combination *= Mod<P>::Inverse( i );
    answer -= combination;
  }
  RETURN( answer );  
}