#796048 (C++17) No.2062 Sum of Subset mod 999630629

提出ソース
結果

問題	No.2062 Sum of Subset mod 999630629
ユーザー	👑 p-adic
提出日時	2022-09-07 13:55:27
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	47,377 bytes
コンパイル時間	3,524 ms
コンパイル使用メモリ	227,336 KB
実行使用メモリ	58,876 KB
最終ジャッジ日時	2023-08-14 18:32:47
合計ジャッジ時間	33,081 ms
ジャッジサーバーID （参考情報）	judge14 / judge13
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,380 KB
testcase_01	AC	2 ms 4,376 KB
testcase_02	AC	2 ms 4,380 KB
testcase_03	AC	2 ms 4,376 KB
testcase_04	AC	1 ms 4,380 KB
testcase_05	AC	2 ms 4,376 KB
testcase_06	AC	2 ms 4,376 KB
testcase_07	AC	1 ms 4,380 KB
testcase_08	AC	10 ms 4,376 KB
testcase_09	AC	8 ms 4,376 KB
testcase_10	AC	7 ms 4,376 KB
testcase_11	AC	2,948 ms 58,876 KB
testcase_12	AC	2,942 ms 58,812 KB
testcase_13	AC	1,371 ms 30,380 KB
testcase_14	AC	3,036 ms 58,576 KB
testcase_15	AC	306 ms 10,808 KB
testcase_16	AC	2,963 ms 56,712 KB
testcase_17	AC	2,952 ms 58,440 KB
testcase_18	AC	1,375 ms 30,364 KB
testcase_19	AC	304 ms 10,516 KB
testcase_20	AC	639 ms 17,512 KB
testcase_21	AC	1,379 ms 31,156 KB
testcase_22	AC	632 ms 17,516 KB
testcase_23	AC	8 ms 4,380 KB
testcase_24	AC	7 ms 4,376 KB
testcase_25	TLE	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include<bits/stdc++.h>
using namespace std;

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

#define CIN( LL , A ) LL A; cin >> A 
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) 
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( ll VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) 
#define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; return 0 

// 以下、自分のライブラリ（https://github.com/p-adic/cpp）よりソースコードをコピーして編集している。
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 <typename T>
using VLArray = list<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-() 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;


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


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;

}


template <typename T> inline constexpr const uint LimitOfPowerForFFT;
template <typename T> inline const T ( &PrimitiveRootOfTwoForFFT() noexcept )[LimitOfPowerForFFT<T>];
template <typename T> inline const T ( &InversePrimitiveRootOfTwoForFFT() noexcept )[LimitOfPowerForFFT<T>];
template <typename T> vector<T> FFT( const vector<T>& f , const uint& N );
template <typename T> vector<T> FFT( const vector<T>& f , const uint& two_power , const uint& exponent );
template <typename T> vector<T> IFFT( const vector<T>& f , const uint& N );
template <typename T> vector<T> IFFT( const vector<T>& f , const uint& two_power , const T& two_power_inv , const uint& exponent );


template <> inline constexpr const uint LimitOfPowerForFFT<Mod<998244353> > = 24;

template <> inline const Mod<998244353> ( &PrimitiveRootOfTwoForFFT() noexcept )[LimitOfPowerForFFT<Mod<998244353> >]
{

  static const Mod<998244353> PRT[ LimitOfPowerForFFT<Mod<998244353> > ] =
    {
      
      Mod<998244353>( 1 ) ,
      Mod<998244353>( 998244352 ) ,
      Mod<998244353>( 911660635 ) ,
      Mod<998244353>( 625715529 ) ,
      Mod<998244353>( 373294451 ) ,
      Mod<998244353>( 827987769 ) ,
      Mod<998244353>( 280333251 ) ,
      Mod<998244353>( 581015842 ) ,
      Mod<998244353>( 628092333 ) ,
      Mod<998244353>( 300892551 ) ,
      Mod<998244353>( 586046298 ) ,
      Mod<998244353>( 615001099 ) ,
      Mod<998244353>( 318017948 ) ,
      Mod<998244353>( 64341522 ) ,
      Mod<998244353>( 106061068 ) ,
      Mod<998244353>( 304605202 ) ,
      Mod<998244353>( 631920086 ) ,
      Mod<998244353>( 857779016 ) ,
      Mod<998244353>( 841431251 ) ,
      Mod<998244353>( 805775211 ) ,
      Mod<998244353>( 390359979 ) ,
      Mod<998244353>( 923521 ) ,
      Mod<998244353>( 961 ) ,
      Mod<998244353>( 31 )

    };

  return PRT;

}

template <> inline const Mod<998244353> ( &InversePrimitiveRootOfTwoForFFT() noexcept )[LimitOfPowerForFFT<Mod<998244353> >]
{

  static const Mod<998244353> PRT[ LimitOfPowerForFFT<Mod<998244353> > ] =
    {
      
      Mod<998244353>( 1 ) ,
      Mod<998244353>( 998244352 ) ,
      Mod<998244353>( 86583718 ) ,
      Mod<998244353>( 488723995 ) ,
      Mod<998244353>( 369330050 ) ,
      Mod<998244353>( 543653592 ) ,
      Mod<998244353>( 382946991 ) ,
      Mod<998244353>( 844956623 ) ,
      Mod<998244353>( 91420391 ) ,
      Mod<998244353>( 433414612 ) ,
      Mod<998244353>( 288894979 ) ,
      Mod<998244353>( 260490556 ) ,
      Mod<998244353>( 857007890 ) ,
      Mod<998244353>( 736054570 ) ,
      Mod<998244353>( 474649464 ) ,
      Mod<998244353>( 948509906 ) ,
      Mod<998244353>( 114942468 ) ,
      Mod<998244353>( 962405921 ) ,
      Mod<998244353>( 667573957 ) ,
      Mod<998244353>( 46809892 ) ,
      Mod<998244353>( 304321983 ) ,
      Mod<998244353>( 30429817 ) ,
      Mod<998244353>( 293967900 ) ,
      Mod<998244353>( 128805723 )

    };

  return PRT;

}

template <typename T> static vector<T> FFT_Body( const vector<T>& f , const uint& two_power , const uint& exponent , const uint& start , const uint& depth , const T ( &PRT )[LimitOfPowerForFFT<T>] );


template <typename T>
vector<T> FFT( const vector<T>& f , const uint& N )
{

  uint two_power = 1;
  uint exponent = 0;
  
  while( N > two_power ){

    two_power *= 2;
    exponent++;

  }

  return FFT<T>( f , two_power , exponent );

}

template <typename T>
vector<T> FFT( const vector<T>& f , const uint& two_power , const uint& exponent )
{

  const uint size = f.size();

  if( size == two_power ){

    return FFT_Body<T>( f , two_power , exponent , 0 , 1 , PrimitiveRootOfTwoForFFT<T>() );
    
  }

  vector<T> f_copy = f;
  const T zero{};

  for( uint i = size ; i < two_power ; i++ ){

    f_copy.push_back( zero );

  }
  
  return FFT_Body<T>( f_copy , two_power , exponent , 0 , 1 , PrimitiveRootOfTwoForFFT<T>() );

}

template <typename T>
vector<T> IFFT( const vector<T>& f , const uint& N )
{

  uint two_power = 1;
  T two_power_inv{ 1 };
  uint exponent = 0;
  
  while( N > two_power ){

    two_power *= 2;
    two_power_inv /= 2;
    exponent++;

  }
  
  return IFFT<T>( f , two_power , two_power_inv , exponent );

}

template <typename T>
vector<T> IFFT( const vector<T>& f , const uint& two_power , const T& two_power_inv , const uint& exponent )
{

  vector<T> answer;
  const uint size = f.size();

  if( size == two_power ){

    answer = move( FFT_Body<T>( f , two_power , exponent , 0 , 1 , InversePrimitiveRootOfTwoForFFT<T>() ) );
    
  } else {

    vector<T> f_copy = f;
    const T zero{};

    for( uint i = size ; i < two_power ; i++ ){

      f_copy.push_back( zero );

    }
  
    answer = move( FFT_Body<T>( f_copy , two_power , exponent , 0 , 1 , InversePrimitiveRootOfTwoForFFT<T>() ) );

  }

  for( uint i = 0 ; i < two_power ; i++ ){

    answer[i] *= two_power_inv;

  }

  return answer;

}

template <typename T>
static vector<T> FFT_Body( const vector<T>& f , const uint& two_power , const uint& exponent , const uint& start , const uint& depth , const T ( &PRT )[LimitOfPowerForFFT<T>] )
{

  vector<T> answer( two_power );

  if( two_power == 1 ){

    answer[0] = ( start < f.size() ? f[ start ] : 0 );
    return answer;

  }

  const uint two_power_sub = two_power / 2;
  const uint exponent_sub = exponent - 1;
  const uint depth_sub = depth * 2;
  vector<T> answer_sub0{ move( FFT_Body<T>( f , two_power_sub , exponent_sub , start , depth_sub , PRT ) ) };
  vector<T> answer_sub1{ move( FFT_Body<T>( f , two_power_sub , exponent_sub , start + depth , depth_sub , PRT ) ) };
  const T& zeta = PRT[exponent];
  T zeta_power{ 1 };

  for( uint i = 0 ; i < two_power ; i++ ){

    const uint i_sub = i % two_power_sub;
    answer[i] = answer_sub0[i_sub] + zeta_power * answer_sub1[i_sub];
    zeta_power *= zeta;

  }

  return answer;

}


template <typename T>
class Polynomial
{

protected:
  vector<T> m_f;
  // m_fのsize
  uint m_size;
  bool m_no_redundant_zero;
  
public:
  inline Polynomial();
  inline Polynomial( const T& t );
  inline Polynomial( const Polynomial<T>& f );
  inline Polynomial( const uint& i , const T& t );

  Polynomial<T>& operator=( const T& t );
  Polynomial<T>& operator=( const Polynomial<T>& f );

  inline const T& operator[]( const uint& i ) const;
  inline T& operator[]( const uint& i );

  inline Polynomial<T>& operator+=( const T& t );
  Polynomial<T>& operator+=( const Polynomial<T>& f );
  inline Polynomial<T>& operator-=( const T& t );
  Polynomial<T>& operator-=( const Polynomial<T>& f );
  Polynomial<T>& operator*=( const T& t );
  Polynomial<T>& operator*=( const Polynomial<T>& f );
  Polynomial<T>& operator/=( const T& t );
  Polynomial<T>& operator%=( const T& t );

  inline Polynomial<T> operator-() const;

  inline const vector<T>& GetCoefficient() const noexcept;
  inline const uint& size() const noexcept;
  
  void RemoveRedundantZero();

  inline string Display() const noexcept;
  
  static inline const Polynomial<T>& zero();
  static inline const T& const_zero();
  static inline const T& const_one();

};

template <typename T>
bool operator==( const Polynomial<T>& f0 , const T& t1 );
template <typename T>
bool operator==( const Polynomial<T>& f0 , const Polynomial<T>& f1 );
template <typename T , typename P> inline bool operator!=( const Polynomial<T>& f0 , const P& f1 );

template <typename T , typename P> inline Polynomial<T> operator+( const Polynomial<T>& f0 , const P& f1 );
template <typename T , typename P> inline Polynomial<T> operator-( const Polynomial<T>& f );
template <typename T , typename P> inline Polynomial<T> operator-( const Polynomial<T>& f0 , const P& f1 );
template <typename T , typename P> inline Polynomial<T> operator*( const Polynomial<T>& f0 , const P& f1 );
template <typename T> inline Polynomial<T> operator/( const Polynomial<T>& f0 , const T& t1 );
template <typename T> inline Polynomial<T> operator%( const Polynomial<T>& f0 , const T& t1 );



template <typename T> inline Polynomial<T>::Polynomial() : m_f() , m_size( 0 ) , m_no_redundant_zero( true ) {}
template <typename T> inline Polynomial<T>::Polynomial( const T& t ) : Polynomial() { if( t != const_zero() ){ operator[]( 0 ) = t; } }
template <typename T> inline Polynomial<T>::Polynomial( const Polynomial<T>& f ) : m_f( f.m_f ) , m_size( f.m_size ) , m_no_redundant_zero( f.m_no_redundant_zero ) {}
template <typename T> inline Polynomial<T>::Polynomial( const uint& i , const T& t ) : Polynomial() { if( t != const_zero() ){ operator[]( i ) = t; } }


template <typename T> inline Polynomial<T>& Polynomial<T>::operator=( const T& t ) { m_f.clear(); m_size = 0; operator[]( 0 ) = t; return *this; }
template <typename T> inline Polynomial<T>& Polynomial<T>::operator=( const Polynomial<T>& f ) { m_f = f.m_f; m_size = f.m_size; m_no_redundant_zero = f.m_no_redundant_zero; return *this; }


template <typename T>
const T& Polynomial<T>::operator[]( const uint& i ) const
{

  if( m_size <= i ){

    return const_zero();

  }
  
  return m_f[i];

}

template <typename T> inline T& Polynomial<T>::operator[]( const uint& i )
{

  m_no_redundant_zero = false;
  const T& z = const_zero();

  while( m_size <= i ){

    m_f.push_back( z );
    m_size++;
    
  }

  return m_f[i];

}

template <typename T> inline Polynomial<T>& Polynomial<T>::operator+=( const T& t ) { operator[]( 0 ) += t; return *this; }

template <typename T>
Polynomial<T>& Polynomial<T>::operator+=( const Polynomial<T>& f )
{

  for( uint i = 0 ; i < f.m_size ; i++ ){

    operator[]( i ) += f.m_f[i];

  }

  return *this;

}

template <typename T> inline Polynomial<T>& Polynomial<T>::operator-=( const T& t ) { operator[]( 0 ) -= t; return *this; }

template <typename T>
Polynomial<T>& Polynomial<T>::operator-=( const Polynomial<T>& f )
{

  for( uint i = 0 ; i < f.m_size ; i++ ){

    operator[]( i ) -= f.m_f[i];

  }

  return *this;

}

template <typename T>
Polynomial<T>& Polynomial<T>::operator*=( const T& t )
{

  if( ! m_no_redundant_zero ){
    
    RemoveRedundantZero();

  }

  if( m_size == 0 || t == const_one() ){

    return *this;

  }

  if( t == const_zero() ){

    return operator=( zero() );

  }
  
  for( uint i = 0 ; i < m_size ; i++ ){

    operator[]( i ) *= t;

  }

  // Tが体である場合は省略可能
  RemoveRedundantZero();
  return *this;

}

template <typename T>
Polynomial<T>& Polynomial<T>::operator*=( const Polynomial<T>& f )
{
  
  if( ! m_no_redundant_zero ){
    
    RemoveRedundantZero();

  }

  if( m_size == 0 ){

    return *this;

  }

  if( f.m_size == 0 ){

    return operator=( zero() );

  }
  
  const uint size = m_size + f.m_size - 1;
  Polynomial<T> product{};  
      
  for( uint i = 0 ; i < size ; i++ ){

    T& product_i = product[i];
    const uint j_min = m_size <= i ? i - m_size + 1 : 0;
    const uint j_lim = i < f.m_size ? i + 1 : f.m_size;
      
    for( uint j = j_min ; j < j_lim ; j++ ){
	
      product_i += m_f[i - j] * f.m_f[j];

    }

  }

  product.RemoveRedundantZero();
  return operator=( product );

}

template <typename T>
Polynomial<T>& Polynomial<T>::operator/=( const T& t )
{
  
  if( ! m_no_redundant_zero ){
    
    RemoveRedundantZero();

  }
  
  for( uint i = 0 ; i < m_size ; i++ ){

    operator[]( i ) /= t;

  }

  // Tが体である場合は省略可能
  RemoveRedundantZero();
  return *this;

}

template <typename T>
Polynomial<T>& Polynomial<T>::operator%=( const T& t )
{

  if( ! m_no_redundant_zero ){
    
    RemoveRedundantZero();

  }

  for( uint i = 0 ; i < m_size ; i++ ){

    operator[]( i ) %= t;

  }

  RemoveRedundantZero();
  return *this;

}

template <typename T> inline Polynomial<T> Polynomial<T>::operator-() const { Polynomial<T>().operator-=( *this ); }

template <typename T> inline const vector<T>& Polynomial<T>::GetCoefficient() const noexcept { return m_f; }
template <typename T> inline const uint& Polynomial<T>::size() const noexcept { return m_size; }

template <typename T>
void Polynomial<T>::RemoveRedundantZero()
{

  if( m_no_redundant_zero ){
    
    return;

  }
  
  const T& z = const_zero();
  
  while( m_size > 0 ? m_f[m_size - 1] == z : false ){

    m_f.pop_back();
    m_size--;

  }

  m_no_redundant_zero = true;
  return;

}

template <typename T>
string Polynomial<T>::Display() const noexcept
{

  string s = "(";

  if( m_size > 0 ){

    s += to_string( m_f[0] );

    for( uint i = 1 ; i < m_size ; i++ ){

      s += "," + to_string( m_f[i] );

    }

  }

  s += ")";
  return s;

}


template <typename T> inline const Polynomial<T>& Polynomial<T>::zero() { static const Polynomial<T> z{}; return z; }
template <typename T> inline const T& Polynomial<T>::const_zero() { static const T z{ 0 }; return z; }
template <typename T> inline const T& Polynomial<T>::const_one() { static const T o{ 1 }; return o; }


template <typename T>
bool operator==( const Polynomial<T>& f0 , const T& t1 )
{

  const uint& size = f0.size();
  const T& zero = Polynomial<T>::const_zero();

  for( uint i = 1 ; i < size ; i++ ){

    if( f0[i] != zero ){

      return false;

    }

  }

  return f0[0] == t1;

}

template <typename T>
bool operator==( const Polynomial<T>& f0 , const Polynomial<T>& f1 )
{

  const uint& size0 = f0.size();
  const uint& size1 = f1.size();
  const uint& size = size0 < size1 ? size1 : size0;

  for( uint i = 0 ; i < size ; i++ ){

    if( f0[i] != f1[i] ){

      return false;

    }

  }

  return true;

}

template <typename T , typename P> inline bool operator!=( const Polynomial<T>& f0 , const P& f1 ) { return !( f0 == f1 ); }

template <typename T , typename P> inline Polynomial<T> operator+( const Polynomial<T>& f0 , const P& f1 ) { Polynomial<T> f = f0; f += f1; return f; }
template <typename T , typename P> inline Polynomial<T> operator-( const Polynomial<T>& f ) { return Polynomial<T>::zero() - f; }
template <typename T , typename P> inline Polynomial<T> operator-( const Polynomial<T>& f0 , const P& f1 ) { Polynomial<T> f = f0; return f.operator-=( f1 ); }
template <typename T , typename P> inline Polynomial<T> operator*( const Polynomial<T>& f0 , const P& f1 ) { Polynomial<T> f = f0; return f.operator*=( f1 ); }
template <typename T> inline Polynomial<T> operator/( const Polynomial<T>& f0 , const T& t1 ) { Polynomial<T> f = f0; return f.operator/=( t1 ); }
template <typename T> inline Polynomial<T> operator%( const Polynomial<T>& f0 , const T& t1 ) { Polynomial<T> f = f0; return f.operator%=( t1 ); }


#define DEFINITION_OF_PARTIAL_SPECIALISATION_OF_MULTIPLICATION_OF_TRUNCATED_POLYNOMIAL( TYPE ) \
  template <> inline TruncatedPolynomial< TYPE >& TruncatedPolynomial< TYPE >::operator*=( const Polynomial< TYPE >& f ) { return TruncatedPolynomial< TYPE >::FFT_Multiplication( f ); } \
  \
  


template <typename T>
class TruncatedPolynomial :
  public Polynomial<T>
{

private:
  // m_N == 0でも動くが、その場合はm_size == 1の時にm_size <= m_Nが成り立たなくなることに注意
  uint m_N;
  
public:
  inline TruncatedPolynomial( const uint& N = 0 );
  inline TruncatedPolynomial( const TruncatedPolynomial<T>& f );
  inline TruncatedPolynomial( const uint& N , const T& t );
  TruncatedPolynomial( const uint& N , const Polynomial<T>& f );
  inline TruncatedPolynomial( const uint& N , const uint& i , const T& t );

  // m_Nも代入されることに注意
  inline TruncatedPolynomial<T>& operator=( const TruncatedPolynomial<T>& f );
  inline TruncatedPolynomial<T>& operator=( const T& t );
  inline TruncatedPolynomial<T>& operator=( const Polynomial<T>& f );

  // m_Nは変化しないことに注意
  inline TruncatedPolynomial<T>& operator+=( const T& t );
  TruncatedPolynomial<T>& operator+=( const Polynomial<T>& f );
  inline TruncatedPolynomial<T>& operator-=( const T& t );
  TruncatedPolynomial<T>& operator-=( const Polynomial<T>& f );
  inline TruncatedPolynomial<T>& operator*=( const T& t );
  TruncatedPolynomial<T>& operator*=( const Polynomial<T>& f );
  inline TruncatedPolynomial<T>& operator/=( const T& t );
  inline TruncatedPolynomial<T>& operator/=( const TruncatedPolynomial<T>& t );
  inline TruncatedPolynomial<T>& operator%=( const T& t );

  inline TruncatedPolynomial<T> operator-() const;

  inline void SetTruncation( const uint& N ) noexcept;
  inline const uint& GetTruncation() const noexcept;

private:
  inline void Truncate();
  // m_N == 0の場合はサポート外
  TruncatedPolynomial<T>& FFT_Multiplication( const Polynomial<T>& f );

};

template <typename T , typename P> inline TruncatedPolynomial<T> operator+( const TruncatedPolynomial<T>& f0 , const P& f1 );
template <typename T , typename P> inline TruncatedPolynomial<T> operator-( const TruncatedPolynomial<T>& f );
template <typename T , typename P> inline TruncatedPolynomial<T> operator-( const TruncatedPolynomial<T>& f0 , const P& f1 );
template <typename T , typename P> inline TruncatedPolynomial<T> operator*( const TruncatedPolynomial<T>& f0 , const P& f1 );
template <typename T , typename P> inline TruncatedPolynomial<T> operator/( const TruncatedPolynomial<T>& f0 , const P& f1 );
template <typename T> inline TruncatedPolynomial<T> operator%( const TruncatedPolynomial<T>& f0 , const T& t1 );

// m_Nが1下がることに注意
template <typename T>
TruncatedPolynomial<T> Differential( const TruncatedPolynomial<T>& f );
// m_Nがi下がることに注意
template <typename T> inline TruncatedPolynomial<T> Differential( const uint& i , const TruncatedPolynomial<T>& f );

// m_Nが1上がることに注意
// Tが標数0またはf.m_N + 1以上の体の場合のみサポート
template <typename T>
TruncatedPolynomial<T> Integral( const TruncatedPolynomial<T>& f );

// f[0]が可逆な場合のみサポート
template <typename T>
TruncatedPolynomial<T> Inverse( const TruncatedPolynomial<T>& f );

// Tが標数0またはf.m_N以上の体でかつf[0] == 0の場合のみサポート
template <typename T>
TruncatedPolynomial<T> Exp( const TruncatedPolynomial<T>& f );

// Tが標数0またはf.m_N以上の体でかつf[0] == 1の場合のみサポート
template <typename T> inline TruncatedPolynomial<T> Log( const TruncatedPolynomial<T>& f );

// Tが標数0またはf.m_N以上の体でかつf[0] == 1の場合のみサポート
template <typename T>
TruncatedPolynomial<T> Power( const TruncatedPolynomial<T>& f , const T& t );



template <typename T> inline TruncatedPolynomial<T>::TruncatedPolynomial( const uint& N ) : Polynomial<T>() , m_N( N ) {}
template <typename T> inline TruncatedPolynomial<T>::TruncatedPolynomial( const TruncatedPolynomial<T>& f ) : Polynomial<T>( f ) , m_N( f.m_N ) {}
template <typename T> inline TruncatedPolynomial<T>::TruncatedPolynomial( const uint& N , const T& t ) : Polynomial<T>( t ) , m_N( N ) {}

template <typename T>
TruncatedPolynomial<T>::TruncatedPolynomial( const uint& N , const Polynomial<T>& f ) : Polynomial<T>() , m_N( N )
{

  const uint& f_size = f.Polynomial<T>::size();
  const uint& size = f_size < m_N ? f_size : m_N;
  
  for( uint i = 0 ; i < size ; i++ ){

    Polynomial<T>::m_f.push_back( f.Polynomial<T>::operator[]( i ) );
    Polynomial<T>::m_size++;
    
  }

}

template <typename T> inline TruncatedPolynomial<T>::TruncatedPolynomial( const uint& N , const uint& i , const T& t ) : Polynomial<T>() , m_N( N ) { if( i < m_N ? t != Polynomial<T>::const_zero() : false ){ Polynomial<T>::operator[]( i ) = t; } }

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator=( const TruncatedPolynomial<T>& f ) { Polynomial<T>::operator=( f ); m_N = f.m_N; return *this; }
template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator=( const T& t ) { Polynomial<T>::operator=( t ); return *this; }
template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator=( const Polynomial<T>& f ) { return operator=( TruncatedPolynomial<T>( m_N , f ) ); }

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator+=( const T& t ) { Polynomial<T>::operator+=( t ); return *this; }

template <typename T>
TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator+=( const Polynomial<T>& f )
{

  const uint& f_size = f.Polynomial<T>::size();
  const uint& size = f_size < m_N ? f_size : m_N;

  for( uint i = 0 ; i < size ; i++ ){

    Polynomial<T>::operator[]( i ) += f.Polynomial<T>::operator[]( i );

  }

  return *this;

}

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator-=( const T& t ) { Polynomial<T>::operator-=( t ); return *this; }

template <typename T>
TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator-=( const Polynomial<T>& f )
{

  const uint& f_size = f.Polynomial<T>::size();
  const uint& size = f_size < m_N ? f_size : m_N;
  
  for( uint i = 0 ; i < size ; i++ ){

    Polynomial<T>::operator[]( i ) -= f.Polynomial<T>::operator[]( i );

  }

  return *this;

}

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator*=( const T& t ) { Polynomial<T>::operator*=( t ); return *this; }

template <typename T>
TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator*=( const Polynomial<T>& f )
{

  if( ! Polynomial<T>::m_no_redundant_zero ){
    
    Polynomial<T>::RemoveRedundantZero();

  }

  if( Polynomial<T>::m_size == 0 ){

    return *this;

  }

  const uint& f_size = f.Polynomial<T>::size();
  
  if( f_size == 0 ){

    return operator=( Polynomial<T>::zero() );

  }
  
  uint size = Polynomial<T>::m_size + f_size - 1;

  if( size >= m_N ){

    size = m_N;

  }

  TruncatedPolynomial<T> product{ m_N , 0 };  
      
  for( uint i = 0 ; i < size ; i++ ){

    T& product_i = product[i];
    const uint j_min = Polynomial<T>::m_size <= i ? i - Polynomial<T>::m_size + 1 : 0;
    const uint j_lim = i < f_size ? i + 1 : f_size;
      
    for( uint j = j_min ; j < j_lim ; j++ ){
	
      product_i += Polynomial<T>::operator[]( i - j ) * f.Polynomial<T>::operator[]( j );

    }

  }

  product.Polynomial<T>::RemoveRedundantZero();
  return operator=( product );

}

DEFINITION_OF_PARTIAL_SPECIALISATION_OF_MULTIPLICATION_OF_TRUNCATED_POLYNOMIAL( Mod<998244353> );

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator/=( const T& t ) { Polynomial<T>::operator/=( t ); return *this; }

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator/=( const TruncatedPolynomial<T>& f ) { return operator*=( Inverse( m_N == f.m_N ? f : TruncatedPolynomial<T>( m_N , f ) ) ); }

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator%=( const T& t ) { Polynomial<T>::operator%=( t ); return *this; }

template <typename T> inline TruncatedPolynomial<T> TruncatedPolynomial<T>::operator-() const { return TruncatedPolynomial<T>( m_N ).operator-=( *this ); }


template <typename T> inline void TruncatedPolynomial<T>::SetTruncation( const uint& N ) noexcept { m_N = N; Truncate(); }
template <typename T> inline const uint& TruncatedPolynomial<T>::GetTruncation() const noexcept { return m_N; }

template <typename T> inline void TruncatedPolynomial<T>::Truncate(){ while( Polynomial<T>::m_size > m_N ){ Polynomial<T>::m_f.pop_back(); Polynomial<T>::m_size--; } }

template <typename T> 
TruncatedPolynomial<T>& TruncatedPolynomial<T>::FFT_Multiplication( const Polynomial<T>& f )
{

  const uint N = m_N * 2 - 1;
  uint two_power = 1;
  T two_power_inv{ 1 };
  uint exponent = 0;
  
  while( N > two_power ){

    two_power *= 2;
    two_power_inv /= 2;
    exponent++;

  }

  vector<T> f0{ move( FFT<T>( Polynomial<T>::m_f , two_power , exponent ) ) };
  const uint& size = f.Polynomial<T>::size();
  const vector<T>& f_m_f = f.Polynomial<T>::GetCoefficient();
  
  vector<T> f1;

  if( size <= m_N ){

    f1 = move( FFT<T>( f_m_f , two_power , exponent ) );
    
  } else {

    for( uint i = 0 ; i < m_N ; i++ ){

      f1.push_back( f_m_f[i] );

    }

    f1 = move( FFT<T>( f1 , two_power , exponent ) );

  }
  
  for( uint i = 0 ; i < two_power ; i++ ){

    f0[i] *= f1[i];
    
  }

  Polynomial<T>::m_f = move( IFFT<T>( f0 , two_power , two_power_inv , exponent ) );
  
  for( uint i = m_N ; i < two_power ; i++ ){

    Polynomial<T>::m_f.pop_back();

  }

  Polynomial<T>::m_size = m_N;
  return *this;
  
}

template <typename T , typename P> inline TruncatedPolynomial<T> operator+( const TruncatedPolynomial<T>& f0 , const P& f1 ) { TruncatedPolynomial<T> f = f0; f += f1; return f; }
template <typename T , typename P> inline TruncatedPolynomial<T> operator-( const TruncatedPolynomial<T>& f ) { return TruncatedPolynomial<T>::zero() - f; }
template <typename T , typename P> inline TruncatedPolynomial<T> operator-( const TruncatedPolynomial<T>& f0 , const P& f1 ) { TruncatedPolynomial<T> f = f0; return f.operator-=( f1 ); }
template <typename T , typename P> inline TruncatedPolynomial<T> operator*( const TruncatedPolynomial<T>& f0 , const P& f1 ) { TruncatedPolynomial<T> f = f0; return f.operator*=( f1 ); }
template <typename T , typename P> inline TruncatedPolynomial<T> operator/( const TruncatedPolynomial<T>& f0 , const P& f1 ) { TruncatedPolynomial<T> f = f0; return f.operator/=( f1 ); }
template <typename T> inline TruncatedPolynomial<T> operator%( const TruncatedPolynomial<T>& f0 , const T& t1 ) { TruncatedPolynomial<T> f = f0; return f.operator%=( t1 ); }


template <typename T>
TruncatedPolynomial<T> Differential( const TruncatedPolynomial<T>& f )
{

  const uint& N = f.GetTruncation();

  if( N == 0 ){

    return TruncatedPolynomial<T>();

  }

  TruncatedPolynomial<T> f_dif{ N - 1 };
  const uint& size = f.size();

  for( uint i = 1 ; i < size ; i++ ){

    f_dif[i - 1] = i * f[i];

  }

  return f_dif;

}

template <typename T> inline TruncatedPolynomial<T> Differential( const uint& i , const TruncatedPolynomial<T>& f ) { return i == 0 ? f : Differential<T>( i - 1 , Differential<T>( f ) ); }

template <typename T>
TruncatedPolynomial<T> Integral( const TruncatedPolynomial<T>& f )
{

  const uint& N = f.GetTruncation();
  TruncatedPolynomial<T> f_int{ N + 1 };
  const uint& size = f.size();

  for( uint i = 1 ; i <= size ; i++ ){

    f_int[i] = f[i - 1] / T( i );

  }

  return f_int;

}

template <typename T>
TruncatedPolynomial<T> Inverse( const TruncatedPolynomial<T>& f )
{

  const uint& N = f.GetTruncation();
  const T& one = Polynomial<T>::const_one();
  const T two = one + one;
  uint power = 1;
  TruncatedPolynomial<T> f_inv{ power , one / f[0] };
  
  while( power < N ){

    power *= 2;
    f_inv.SetTruncation( power );
    f_inv *= - f_inv * f + two;
    
  }

  f_inv.SetTruncation( N );
  return f_inv;
  
}

template <typename T>
TruncatedPolynomial<T> Exp( const TruncatedPolynomial<T>& f )
{

  const uint& N = f.GetTruncation();
  const T& one = Polynomial<T>::const_one();
  uint power = 1;
  TruncatedPolynomial<T> f_exp{ power , one };
  
  while( power < N ){

    power *= 2;
    f_exp.SetTruncation( power );
    f_exp *= - Log( f_exp ) + f + one;
   
  }

  f_exp.SetTruncation( N );
  return f_exp;
  
}

template <typename T> inline TruncatedPolynomial<T> Log( const TruncatedPolynomial<T>& f ) { return Integral<T>( Differential<T>( f ) / f ); }

template <typename T> inline TruncatedPolynomial<T> Power( const TruncatedPolynomial<T>& f , const T& t ) { return Exp( Log( f ) * t ); }


constexpr const ll P = 998244353;
constexpr const ll Q = 999630629;
using MOD = Mod<P>;

int main(){
  UNTIE;
  CIN( ll , N );
  ll A[100000];
  ll sum = 0;
  FOR( i , 0 , N ){
    ll& Ai = A[i];
    cin >> Ai;
    sum += Ai;
  }
  MOD coef{};
  MOD one = MOD( 1 );
  ll D_signed = sum - Q + 1;
  if( D_signed > 0 ){
    sort( A , A + N );
    uint B[100000];
    ll count[100000];
    ll Ai_prev = 0;
    ll num = -1;
    FOR( i , 0 , N ){
      ll& Ai = A[i];
      if( Ai_prev == Ai ){
	count[num]++;
      } else if( Ai < D_signed ){
	num++;
	B[num] = uint( Ai );
	count[num] = 1;
	Ai_prev = Ai;
      } else {
	i = N;
      }
    }
    uint D = uint( D_signed );
    TruncatedPolynomial<MOD> f{ D };
    num++;
    FOR( i , 0 , num ){
      uint& Bi = B[i];
      MOD count_i{ count[i] };
      uint j_lim = ( D - 1 ) / Bi + 1;
      uint d = 0;
      FOR( j , 1 , j_lim ){
      	d += Bi;
      	if( j % 2 == 0 ){
      	  f[d] -= count_i / j;
      	} else {
      	  f[d] += count_i / j;
      	}
      }
    }
    f = Exp<MOD>( f );
    FOR( i , 0 , D ){
      coef += f[i];
    }
  }
  MOD m{ one };
  MOD power{ 2 };
  N--;
  while( N != 0 ){
    if( N % 2 == 1 ){
      m *= power;
    }
    power = power * power;
    N /= 2;
  }
  RETURN( ( m * sum - coef * Q ).Represent() );
}
yukicoder

結果

テストケース

ソースコード
