結果
問題 | No.1815 K色問題 |
ユーザー | 👑 p-adic |
提出日時 | 2022-07-18 23:26:36 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 50,286 bytes |
コンパイル時間 | 2,386 ms |
コンパイル使用メモリ | 122,904 KB |
実行使用メモリ | 22,988 KB |
最終ジャッジ日時 | 2024-09-29 22:45:46 |
合計ジャッジ時間 | 6,019 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
13,632 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,816 KB |
testcase_03 | AC | 2 ms
6,816 KB |
testcase_04 | AC | 2 ms
6,820 KB |
testcase_05 | AC | 2 ms
6,820 KB |
testcase_06 | AC | 93 ms
22,988 KB |
testcase_07 | AC | 23 ms
7,888 KB |
testcase_08 | TLE | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
ソースコード
#include <iostream> #include <list> #include <vector> #include <string> #include <stdio.h> #include <stdint.h> #include <chrono> using namespace std; using ll = long long; using INT_TYPE_FOR_MOD = ll; using INT_TYPE_FOR_ADIC_INT = ll; template <typename T> using VLArray = list<T>; #define PRIME_NUMBER 1000000007 #define MOD Mod<PRIME_NUMBER> // 自分のライブラリ(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 <INT_TYPE_FOR_ADIC_INT P , INT_TYPE_FOR_ADIC_INT LENGTH = 0> class AdicInt { private: VLArray<INT_TYPE_FOR_ADIC_INT> m_expansion; INT_TYPE_FOR_ADIC_INT m_n; public: inline AdicInt( const INT_TYPE_FOR_ADIC_INT& n ) noexcept; inline const VLArray<INT_TYPE_FOR_ADIC_INT>& GetExpansion() const noexcept; inline const INT_TYPE_FOR_ADIC_INT& GetValue() const noexcept; static const VLArray<INT_TYPE_FOR_ADIC_INT>& Expand( const INT_TYPE_FOR_ADIC_INT& n ) noexcept; }; template <INT_TYPE_FOR_ADIC_INT P , INT_TYPE_FOR_ADIC_INT LENGTH> inline AdicInt<P,LENGTH>::AdicInt( const INT_TYPE_FOR_ADIC_INT& n ) noexcept : m_expansion( Expand( n ) ) , m_n( n ) {} template <INT_TYPE_FOR_ADIC_INT P , INT_TYPE_FOR_ADIC_INT LENGTH> inline const VLArray<INT_TYPE_FOR_ADIC_INT>& AdicInt<P,LENGTH>::GetExpansion() const noexcept { return m_expansion; } template <INT_TYPE_FOR_ADIC_INT P , INT_TYPE_FOR_ADIC_INT LENGTH> inline const INT_TYPE_FOR_ADIC_INT& AdicInt<P,LENGTH>::GetValue() const noexcept { return m_n; } template <INT_TYPE_FOR_ADIC_INT P , INT_TYPE_FOR_ADIC_INT LENGTH> const VLArray<INT_TYPE_FOR_ADIC_INT>& AdicInt<P,LENGTH>::Expand( const INT_TYPE_FOR_ADIC_INT& n ) noexcept { static VLArray<INT_TYPE_FOR_ADIC_INT> memory_n{}; static VLArray<VLArray<INT_TYPE_FOR_ADIC_INT> > memory_answer{}; if( P == 0 ){ // ダミー return memory_n; } auto itr_n = memory_n.begin() , end_n = memory_n.end(); auto itr_answer = memory_answer.begin(); while( itr_n != end_n ){ if( *itr_n == n ){ return *itr_answer; } itr_n++; itr_answer++; } INT_TYPE_FOR_ADIC_INT n_copy = n; VLArray<INT_TYPE_FOR_ADIC_INT> answer{}; if( LENGTH == 0 ){ for( INT_TYPE_FOR_ADIC_INT i = 0 ; n_copy != 0 ; i++ ){ const INT_TYPE_FOR_ADIC_INT d = Residue<INT_TYPE_FOR_ADIC_INT>( P , n_copy ); answer.push_back( d ); n_copy -= d; n_copy /= P; } } else { for( INT_TYPE_FOR_ADIC_INT i = 0 ; i < LENGTH && n_copy != 0 ; i++ ){ const INT_TYPE_FOR_ADIC_INT d = Residue<INT_TYPE_FOR_ADIC_INT>( P , n_copy ); answer.push_back( d ); n_copy -= d; n_copy /= P; } } memory_n.push_back( n ); memory_answer.push_back( answer ); return memory_answer.back(); } // init * ( t ^ num ) template <typename T , typename UINT> T Power( const T& t , const UINT& num , const T& init = 1 , const bool& for_right_multiplication = true , const string& method = "normal" ); template <typename T , typename UINT> inline T PowerNormalMethod( const T& t , const UINT& num , const T& init = 1 , const bool& for_right_multiplication = true ); template <typename T , typename UINT> T PowerBinaryMethod( const T& t , const UINT& num , const T& init = 1 , const bool& for_right_multiplication = true ); template <typename T , typename UINT> inline T Power( const T& t , const UINT& num , const T& init , const bool& for_right_multiplication , const string& method ) { return method == "binary" ? PowerBinaryMethod<T,UINT>( t , num , init , for_right_multiplication ) : PowerNormalMethod<T,UINT>( t , num , init , for_right_multiplication ); } template <typename T , typename UINT> inline T PowerNormalMethod( const T& t , const UINT& num , const T& init , const bool& for_right_multiplication ) { return num == 0 ? init : ( for_right_multiplication ? PowerNormalMethod<T,UINT>( t , num - 1 , init ) * t : t * PowerNormalMethod<T,UINT>( t , num - 1 , init ) ); } template <typename T , typename UINT> T PowerBinaryMethod( const T& t , const UINT& num , const T& init , const bool& for_right_multiplication ) { const VLArray<UINT>& num_binary = AdicInt<2>::Expand( num ); T answer = init; T power = t; for( auto itr = num_binary.begin() , end = num_binary.end() ; itr != end ; itr++ ){ if( *itr == 1 ){ answer = for_right_multiplication ? answer * power : power * answer; } power = power * power; } return answer; } // ここをtempate <typename INT , INT M>などにしてしまうとoperator+などを呼び出す際に型推論に失敗する。整数型を変えたい時はINT_TYPE_FOR_MODの型エイリアスを変更する。 template <INT_TYPE_FOR_MOD M> class Mod { protected: INT_TYPE_FOR_MOD m_n; INT_TYPE_FOR_MOD m_inv; public: inline Mod() noexcept; inline Mod( const INT_TYPE_FOR_MOD& n ) noexcept; inline Mod( const Mod<M>& n ) noexcept; inline Mod<M>& operator=( const INT_TYPE_FOR_MOD& n ) noexcept; Mod<M>& operator=( const Mod<M>& n ) noexcept; Mod<M>& operator+=( const INT_TYPE_FOR_MOD& n ) noexcept; inline Mod<M>& operator+=( const Mod<M>& n ) noexcept; inline Mod<M>& operator-=( const INT_TYPE_FOR_MOD& n ) noexcept; inline Mod<M>& operator-=( const Mod<M>& n ) noexcept; Mod<M>& operator*=( const INT_TYPE_FOR_MOD& n ) noexcept; Mod<M>& operator*=( const Mod<M>& n ) noexcept; // INT_TYPE_FOR_MODでの割り算ではないことに注意 virtual Mod<M>& operator/=( const INT_TYPE_FOR_MOD& n ); virtual Mod<M>& operator/=( const Mod<M>& n ); Mod<M>& operator%=( const INT_TYPE_FOR_MOD& n ); inline Mod<M>& operator%=( const Mod<M>& n ); // 前置++/--を使うつもりがないので後置++/--と同じものとして定義する inline Mod<M>& operator++() noexcept; inline Mod<M>& operator++( int ) noexcept; inline Mod<M>& operator--() noexcept; inline Mod<M>& operator--( int ) noexcept; inline const INT_TYPE_FOR_MOD& Represent() const noexcept; void Invert() noexcept; bool CheckInvertible() noexcept; bool IsSmallerThan( const INT_TYPE_FOR_MOD& n ) const noexcept; bool IsBiggerThan( const INT_TYPE_FOR_MOD& n ) const noexcept; }; template <INT_TYPE_FOR_MOD M> inline bool operator==( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline bool operator==( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline bool operator==( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline bool operator==( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline bool operator!=( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline bool operator!=( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline bool operator!=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline bool operator!=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline bool operator<( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline bool operator<( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline bool operator<( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline bool operator<=( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline bool operator<=( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline bool operator<=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline bool operator<=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline bool operator>( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline bool operator>( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline bool operator>( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline bool operator>( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline bool operator>=( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline bool operator>=( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline bool operator>=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline bool operator>=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> Mod<M> operator+( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> Mod<M> operator+( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> Mod<M> operator+( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> inline Mod<M> operator-( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> Mod<M> operator-( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> Mod<M> operator-( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> Mod<M> operator*( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> Mod<M> operator*( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> Mod<M> operator*( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept; template <INT_TYPE_FOR_MOD M> Mod<M> operator/( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ); template <INT_TYPE_FOR_MOD M> Mod<M> operator/( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ); template <INT_TYPE_FOR_MOD M> Mod<M> operator/( const Mod<M>& n0 , const Mod<M>& n1 ); template <INT_TYPE_FOR_MOD M> Mod<M> operator%( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ); template <INT_TYPE_FOR_MOD M> inline Mod<M> operator%( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ); template <INT_TYPE_FOR_MOD M> inline Mod<M> operator%( const Mod<M>& n0 , const Mod<M>& n1 ); template <INT_TYPE_FOR_MOD M> Mod<M> Inverse( const Mod<M>& n ); template <INT_TYPE_FOR_MOD M> Mod<M> Power( const Mod<M>& n , const INT_TYPE_FOR_MOD& p , const string& method = "normal" ); // M乗が1になるよう定義されていることに注意 template <INT_TYPE_FOR_MOD M> inline Mod<M> Power( const Mod<M>& n , const Mod<M>& p , const string& method = "normal" ); void LazyEvaluationOfModularInverse( const INT_TYPE_FOR_MOD& M , const INT_TYPE_FOR_MOD& n , INT_TYPE_FOR_MOD& m ); template <INT_TYPE_FOR_MOD M> inline Mod<M>::Mod() noexcept : m_n( 0 ) , m_inv( M ){} template <INT_TYPE_FOR_MOD M> inline Mod<M>::Mod( const INT_TYPE_FOR_MOD& n ) noexcept : m_n( Residue<INT_TYPE_FOR_MOD>( M , n ) ) , m_inv( 0 ){} template <INT_TYPE_FOR_MOD M> inline Mod<M>::Mod( const Mod<M>& n ) noexcept : m_n( n.m_n ) , m_inv( 0 ){} template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator=( const INT_TYPE_FOR_MOD& n ) noexcept { return operator=( Mod<M>( n ) ); } template <INT_TYPE_FOR_MOD M> Mod<M>& Mod<M>::operator=( const Mod<M>& n ) noexcept { m_n = n.m_n; m_inv = n.m_inv; return *this; } template <INT_TYPE_FOR_MOD M> Mod<M>& Mod<M>::operator+=( const INT_TYPE_FOR_MOD& n ) noexcept { m_n = Residue<INT_TYPE_FOR_MOD>( M , m_n + n ); m_inv = 0; return *this; } template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator+=( const Mod<M>& n ) noexcept { return operator+=( n.m_n ); }; template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator-=( const INT_TYPE_FOR_MOD& n ) noexcept { return operator+=( -n ); } template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator-=( const Mod<M>& n ) noexcept { return operator-=( n.m_n ); } template <INT_TYPE_FOR_MOD M> Mod<M>& Mod<M>::operator*=( const INT_TYPE_FOR_MOD& n ) noexcept { m_n = Residue<INT_TYPE_FOR_MOD>( M , m_n * n ); m_inv = 0; return *this; } template <INT_TYPE_FOR_MOD M> Mod<M>& Mod<M>::operator*=( const Mod<M>& n ) noexcept { m_n = Residue<INT_TYPE_FOR_MOD>( M , m_n * n.m_n ); if( m_inv == 0 || n.m_inv == 0 ){ m_inv = 0; } else if( m_inv == M || n.m_inv == M ){ m_inv = M; } else { Residue<INT_TYPE_FOR_MOD>( M , m_inv * n.m_inv ); } return *this; } // 仮想関数なのでinline指定しない。 template <INT_TYPE_FOR_MOD M> Mod<M>& Mod<M>::operator/=( const INT_TYPE_FOR_MOD& n ) { return operator/=( Mod<M>( n ) ); } template <INT_TYPE_FOR_MOD M> Mod<M>& Mod<M>::operator/=( const Mod<M>& n ) { return operator*=( Inverse( n ) ); } template <INT_TYPE_FOR_MOD M> Mod<M>& Mod<M>::operator%=( const INT_TYPE_FOR_MOD& n ) { m_n %= Residue<INT_TYPE_FOR_MOD>( M , n ); m_inv = 0; return *this; } template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator%=( const Mod<M>& n ) { return operator%=( n.m_n ); } template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator++() noexcept { return operator+=( 1 ); } template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator++( int ) noexcept { return operator++(); } template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator--() noexcept { return operator-=( 1 ); } template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator--( int ) noexcept { return operator-=(); } template <INT_TYPE_FOR_MOD M> inline const INT_TYPE_FOR_MOD& Mod<M>::Represent() const noexcept { return m_n; } template <INT_TYPE_FOR_MOD M> void Mod<M>::Invert() noexcept { if( CheckInvertible() ){ INT_TYPE_FOR_MOD i = m_inv; m_inv = m_n; m_n = i; } else { // m_nがMになるのはここの処理に限るのでRepresent()の値を参照することで例外処理可能 m_n = M; m_inv = M; } return; } template <INT_TYPE_FOR_MOD M> bool Mod<M>::CheckInvertible() noexcept { if( m_inv == 0 ){ LazyEvaluationOfModularInverse( M , m_n , m_inv ); } return m_inv != M; } template <INT_TYPE_FOR_MOD M> inline bool Mod<M>::IsSmallerThan( const INT_TYPE_FOR_MOD& n ) const noexcept { return m_n < Residue<INT_TYPE_FOR_MOD>( M , n ); } template <INT_TYPE_FOR_MOD M> inline bool Mod<M>::IsBiggerThan( const INT_TYPE_FOR_MOD& n ) const noexcept { return m_n > Residue<INT_TYPE_FOR_MOD>( M , n ); } template <INT_TYPE_FOR_MOD M> inline bool operator==( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { return n0 == Mod<M>( n1 ); } template <INT_TYPE_FOR_MOD M> inline bool operator==( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return Mod<M>( n0 ) == n0; } template <INT_TYPE_FOR_MOD M> inline bool operator==( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return n0.Represent() == n1.Represent(); } template <INT_TYPE_FOR_MOD M> inline bool operator!=( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { return !( n0 == n1 ); } template <INT_TYPE_FOR_MOD M> inline bool operator!=( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return !( n0 == n1 ); } template <INT_TYPE_FOR_MOD M> inline bool operator!=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return !( n0 == n1 ); } template <INT_TYPE_FOR_MOD M> inline bool operator<( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { return n0.IsSmallerThan( n1 ); } template <INT_TYPE_FOR_MOD M> inline bool operator<( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return n1.IsBiggerThan( n0 ); } template <INT_TYPE_FOR_MOD M> inline bool operator<( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return n0.Represent() < n1.Represent(); } template <INT_TYPE_FOR_MOD M> inline bool operator<=( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { return !( n1 < n0 ); } template <INT_TYPE_FOR_MOD M> inline bool operator<=( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return !( n1 < n0 ); } template <INT_TYPE_FOR_MOD M> inline bool operator<=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return !( n1 < n0 ); } template <INT_TYPE_FOR_MOD M> inline bool operator>( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { return n1 < n0; } template <INT_TYPE_FOR_MOD M> inline bool operator>( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return n1 < n0; } template <INT_TYPE_FOR_MOD M> inline bool operator>( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return n1 < n0; } template <INT_TYPE_FOR_MOD M> inline bool operator>=( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { return !( n0 < n1 ); } template <INT_TYPE_FOR_MOD M> inline bool operator>=( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return !( n0 < n1 ); } template <INT_TYPE_FOR_MOD M> inline bool operator>=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return !( n0 < n1 ); } template <INT_TYPE_FOR_MOD M> Mod<M> operator+( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { auto n = n0; n += n1; return n; } template <INT_TYPE_FOR_MOD M> inline Mod<M> operator+( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return n1 + n0; } template <INT_TYPE_FOR_MOD M> inline Mod<M> operator+( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return n0 + n1.Represent(); } template <INT_TYPE_FOR_MOD M> inline Mod<M> operator-( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { return n0 + ( -n1 ); } template <INT_TYPE_FOR_MOD M> inline Mod<M> operator-( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return Mod<M>( n0 - n1.Represent() ); } template <INT_TYPE_FOR_MOD M> inline Mod<M> operator-( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return n0 - n1.Represent(); } template <INT_TYPE_FOR_MOD M> Mod<M> operator*( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { auto n = n0; n *= n1; return n; } template <INT_TYPE_FOR_MOD M> inline Mod<M> operator*( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return n1 * n0; } template <INT_TYPE_FOR_MOD M> Mod<M> operator*( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { auto n = n0; n *= n1; return n; } template <INT_TYPE_FOR_MOD M> inline Mod<M> operator/( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) { return n0 / Mod<M>( n1 ); } template <INT_TYPE_FOR_MOD M> inline Mod<M> operator/( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) { return Mod<M>( n0 ) / n1; } template <INT_TYPE_FOR_MOD M> Mod<M> operator/( const Mod<M>& n0 , const Mod<M>& n1 ) { auto n = n0; n /= n1; return n; } template <INT_TYPE_FOR_MOD M> Mod<M> operator%( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) { auto n = n0; n %= n1; return n; } template <INT_TYPE_FOR_MOD M> inline Mod<M> operator%( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) { return Mod<M>( n0 ) % n1.Represent(); } template <INT_TYPE_FOR_MOD M> inline Mod<M> operator%( const Mod<M>& n0 , const Mod<M>& n1 ) { return n0 % n1.Represent(); } template <INT_TYPE_FOR_MOD M> Mod<M> Inverse( const Mod<M>& n ) { auto n_copy = n; n_copy.Invert(); return n_copy; } template <INT_TYPE_FOR_MOD M> Mod<M> Power( const Mod<M>& n , const INT_TYPE_FOR_MOD& p , const string& method ) { if( p >= 0 ){ return Power<Mod<M>,INT_TYPE_FOR_MOD>( n , p , 1 , true , true , method ); } return Inverse( Power<M>( n , -p , method ) ); } template <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 ); } void LazyEvaluationOfModularInverse( const INT_TYPE_FOR_MOD& M , const INT_TYPE_FOR_MOD& n , INT_TYPE_FOR_MOD& m ) { static VLArray<INT_TYPE_FOR_MOD> memory_M{}; // vectorでなくVLArrayだと引数が小さい順に呼び出した時の計算量がO(1)からO(n)に跳ね上がってしまう。 static VLArray<vector<INT_TYPE_FOR_MOD> > memory_inverse{}; auto itr_M = memory_M.begin() , end_M = memory_M.end(); auto itr_inverse = memory_inverse.begin(); vector<INT_TYPE_FOR_MOD>* p_inverse = nullptr; while( itr_M != end_M && p_inverse == nullptr ){ if( *itr_M == M ){ p_inverse = &( *itr_inverse ); } itr_M++; itr_inverse++; } if( p_inverse == nullptr ){ memory_M.push_front( M ); memory_inverse.push_front( vector<INT_TYPE_FOR_MOD>() ); p_inverse = &( memory_inverse.front() ); p_inverse->push_back( M ); } const INT_TYPE_FOR_MOD size = p_inverse->size(); for( INT_TYPE_FOR_MOD i = size ; i <= n ; i++ ){ p_inverse->push_back( 0 ); } INT_TYPE_FOR_MOD& n_inv = ( *p_inverse )[n]; if( n_inv != 0 ){ m = n_inv; return; } const INT_TYPE_FOR_MOD M_abs = M >= 0 ? M : -M; const INT_TYPE_FOR_MOD n_sub = M_abs % n; INT_TYPE_FOR_MOD n_sub_inv = ( *p_inverse )[n_sub]; if( n_sub_inv == 0 ){ LazyEvaluationOfModularInverse( M , n_sub , n_sub_inv ); } if( n_sub_inv != M ){ n_inv = M_abs - ( ( n_sub_inv * ( M_abs / n ) ) % M_abs ); m = n_inv; return; } for( INT_TYPE_FOR_MOD i = 1 ; i < M_abs ; i++ ){ if( ( n * i ) % M_abs == 1 ){ n_inv = i; m = n_inv; return; } } n_inv = M; m = n_inv; return; } // 階乗(INT = Mod<M>の時にMでの値が1であることに注意) template <typename INT> inline INT Factorial( const INT& n , const INT& n_min = 1 , const string& mode = "normal" ); // modular階乗(INT1 = Mod<M>の時にMでの値が0であることに注意) template <typename INT1 , typename INT2> inline INT1 ModularFactorial( const INT2& n , const INT2& n_min = 1 , const string& mode = "normal" ); // 再帰式(呼び出し順によっては再帰深度が大きい) template <typename INT1 , typename INT2> const INT1& ModularFactorialNormalMethod( const INT2& n ); template <typename INT1 , typename INT2> const INT1& ModularFactorialNormalMethod( const INT2& n , const INT2& n_min ); template <typename INT1 , typename INT2> const INT1& ModularFactorialNormalMethod_Body( const INT2& n , const INT2& n_min ); // ループ template <typename INT1 , typename INT2> INT1 ModularFactorialLoopMethod( const INT2& n , const INT2& n_min = 1 ); // modular階乗の逆数(INT1 = Mod<M>の時にMでの値がサポート外であることに注意) template <typename INT1 , typename INT2> inline INT1 ModularFactorialInverse( const INT2& n , const INT2& n_min = 1 , const string& mode = "normal" ); // 再帰式(呼び出し順によっては再帰深度が大きい) template <typename INT1 , typename INT2> const INT1& ModularFactorialInverseNormalMethod( const INT2& n ); template <typename INT1 , typename INT2> const INT1& ModularFactorialInverseNormalMethod( const INT2& n , const INT2& n_min ); template <typename INT1 , typename INT2> const INT1& ModularFactorialInverseNormalMethod_Body( const INT2& n , const INT2& n_min ); // ループ template <typename INT1 , typename INT2> INT1 ModularFactorialInverseLoopMethod( const INT2& n , const INT2& n_min = 1 ); // 場合の数 template <typename INT> INT Combination( const INT& n , const INT& m , const string& mode = "normal" ); // 再帰式(呼び出し順によっては再帰深度が大きい) template <typename INT> const INT& CombinationNormalMethod( const INT& n , const INT& m ); // ループ(割り算回数が大きい) template <typename INT> INT CombinationLoopMethod( const INT& n , const INT& m ); // 階乗の比(modular演算でない時はオーバーフローしやすい) template <typename INT> inline INT CombinationFactorialNormalMethod( const INT& n , const INT& m ); template <typename INT> inline INT CombinationFactorialLoopMethod( const INT& n , const INT& m ); template <typename INT> inline INT CombinationModularFactorialInverseNormalMethod( const INT& n , const INT& m ); template <typename INT> inline INT CombinationModularFactorialInverseLoopMethod( const INT& n , const INT& m ); template <typename INT> inline INT Factorial( const INT& n , const INT& n_min , const string& mode ) { return ModularFactorial<INT,INT>( n , n_min , mode ); } template <typename INT1 , typename INT2> inline INT1 ModularFactorial( const INT2& n , const INT2& n_min , const string& mode ) { return mode == "loop" ? ModularFactorialLoopMethod<INT1,INT2>( n , n_min ) : ModularFactorialNormalMethod<INT1,INT2>( n , n_min ); } template <typename INT1 , typename INT2> const INT1& ModularFactorialNormalMethod( const INT2& n ) { // const参照返しなので静的const変数を返す。 if( n < 1 ){ static const INT1 one = 1; return one; } static VLArray<INT2> memory_n{}; static VLArray<INT1> memory_answer{}; auto itr_n = memory_n.begin() , end_n = memory_n.end(); auto itr_answer = memory_answer.begin(); while( itr_n != end_n ){ if( *itr_n == n ){ return *itr_answer; } itr_n++; itr_answer++; } const INT1 answer = n * ModularFactorialNormalMethod<INT1,INT2>( n - 1 ); memory_n.push_front( n ); memory_answer.push_front( answer ); return memory_answer.front(); } template <typename INT1 , typename INT2> const INT1& ModularFactorialNormalMethod( const INT2& n , const INT2& n_min ) { if( n_min == 1 ){ return ModularFactorialNormalMethod<INT1,INT2>( n ); } return ModularFactorialNormalMethod_Body<INT1,INT2>( n , n_min ); } template <typename INT1 , typename INT2> const INT1& ModularFactorialNormalMethod_Body( const INT2& n , const INT2& n_min ) { // const参照返しなので静的const変数を返す。 if( n < n_min ){ static const INT1 one = 1; return one; } static VLArray<INT2> memory_n{}; static VLArray<VLArray<INT2> > memory_n_min{}; static VLArray<VLArray<INT1> > memory_answer{}; VLArray<INT2>* p_n_min = nullptr; VLArray<INT1>* p_answer = nullptr; auto itr_n = memory_n.begin() , end_n = memory_n.end(); auto itr_n_min = memory_n_min.begin(); auto itr_answer = memory_answer.begin(); while( itr_n != end_n && p_n_min == nullptr ){ if( *itr_n == n ){ p_n_min = &( *itr_n_min ); p_answer = &( *itr_answer ); } itr_n++; itr_n_min++; itr_answer++; } if( p_n_min == nullptr ){ memory_n.push_front( n ); memory_n_min.push_front( VLArray<INT2>() ); memory_answer.push_front( VLArray<INT1>() ); p_n_min = &( memory_n_min.front() ); p_answer = &( memory_answer.front() ); } auto itr_n_min_current = p_n_min->begin() , end_n_min_current = p_n_min->end(); auto itr_answer_current = p_answer->begin(); while( itr_n_min_current != end_n_min_current ){ if( *itr_n_min_current == n_min ){ return *itr_answer_current; } itr_n_min_current++; itr_answer_current++; } const INT1 answer = ModularFactorialNormalMethod<INT1,INT2>( n , n_min + 1 ) * n_min; p_n_min->push_front( n_min ); p_answer->push_front( answer ); return p_answer->front(); } template <typename INT1 , typename INT2> INT1 ModularFactorialLoopMethod( const INT2& n , const INT2& n_min ) { INT1 f = 1; for( INT2 i = n_min ; i <= n ; i++ ){ f *= i; } return f; } template <typename INT1 , typename INT2> inline INT1 ModularFactorialInverse( const INT2& n , const INT2& n_min , const string& mode ) { return mode == "loop" ? ModularFactorialInverseLoopMethod<INT1,INT2>( n , n_min ) : ModularFactorialInverseNormalMethod<INT1,INT2>( n , n_min ); } template <typename INT1 , typename INT2> const INT1& ModularFactorialInverseNormalMethod( const INT2& n ) { // const参照返しなので静的const変数を返す。 if( n < 1 ){ static const INT1 one = 1; return one; } static VLArray<INT2> memory_n{}; static VLArray<INT1> memory_answer{}; auto itr_n = memory_n.begin() , end_n = memory_n.end(); auto itr_answer = memory_answer.begin(); while( itr_n != end_n ){ if( *itr_n == n ){ return *itr_answer; } itr_n++; itr_answer++; } const INT1 answer = ModularFactorialInverseNormalMethod<INT1,INT2>( n - 1 ) / n; memory_n.push_front( n ); memory_answer.push_front( answer ); return memory_answer.front(); } template <typename INT1 , typename INT2> const INT1& ModularFactorialInverseNormalMethod( const INT2& n , const INT2& n_min ) { if( n_min == 1 ){ return ModularFactorialInverseNormalMethod<INT1,INT2>( n ); } return ModularFactorialInverseNormalMethod_Body<INT1,INT2>( n , n_min ); } template <typename INT1 , typename INT2> const INT1& ModularFactorialInverseNormalMethod_Body( const INT2& n , const INT2& n_min ) { // const参照返しなので静的const変数を返す。 if( n < n_min ){ static const INT1 one = 1; return one; } static VLArray<INT2> memory_n{}; static VLArray<VLArray<INT2> > memory_n_min{}; static VLArray<VLArray<INT1> > memory_answer{}; VLArray<INT2>* p_n_min = nullptr; VLArray<INT1>* p_answer = nullptr; auto itr_n = memory_n.begin() , end_n = memory_n.end(); auto itr_n_min = memory_n_min.begin(); auto itr_answer = memory_answer.begin(); while( itr_n != end_n && p_n_min == nullptr ){ if( *itr_n == n ){ p_n_min = &( *itr_n_min ); p_answer = &( *itr_answer ); } itr_n++; itr_n_min++; itr_answer++; } if( p_n_min == nullptr ){ memory_n.push_front( n ); memory_n_min.push_front( VLArray<INT2>() ); memory_answer.push_front( VLArray<INT1>() ); p_n_min = &( memory_n_min.front() ); p_answer = &( memory_answer.front() ); } auto itr_n_min_current = p_n_min->begin() , end_n_min_current = p_n_min->end(); auto itr_answer_current = p_answer->begin(); while( itr_n_min_current != end_n_min_current ){ if( *itr_n_min_current == n_min ){ return *itr_answer_current; } itr_n_min_current++; itr_answer_current++; } const INT1 answer = ModularFactorialInverseNormalMethod<INT1,INT2>( n , n_min + 1 ) / (INT1)n_min; p_n_min->push_front( n_min ); p_answer->push_front( answer ); return p_answer->front(); } template <typename INT1 , typename INT2> INT1 ModularFactorialInverseLoopMethod( const INT2& n , const INT2& n_min ) { INT1 f = 1; for( INT2 i = n_min ; i <= n ; i++ ){ f /= i; } return f; } template <typename INT> INT Combination( const INT& n , const INT& m , const string& mode ) { if( n < m ){ return 0; } if( mode == "loop" ){ return CombinationLoopMethod<INT>( n , m ); } if( mode == "factorial normal" ){ return CombinationFactorialNormalMethod<INT>( n , m ); } if( mode == "factorial loop" ){ return CombinationFactorialLoopMethod<INT>( n , m ); } if( mode == "modular factorial inverse normal" ){ return CombinationModularFactorialInverseNormalMethod<INT>( n , m ); } if( mode == "modular factorial inverse loop" ){ return CombinationModularFactorialInverseLoopMethod<INT>( n , m ); } return CombinationNormalMethod<INT>( n , m ); } template <typename INT> const INT& CombinationNormalMethod( const INT& n , const INT& m ) { // const参照返しなので静的const変数を返す。 if( m == 0 ){ static const INT one = 1; return one; } static VLArray<INT> memory_n{}; static VLArray<VLArray<INT> > memory_m{}; static VLArray<VLArray<INT> > memory_answer{}; VLArray<INT>* p_m = nullptr; VLArray<INT>* p_answer = nullptr; auto itr_n = memory_n.begin() , end_n = memory_n.end(); auto itr_m = memory_m.begin(); auto itr_answer = memory_answer.begin(); while( itr_n != end_n && p_m == nullptr ){ if( *itr_n == n ){ p_m = &( *itr_m ); p_answer = &( *itr_answer ); } itr_n++; itr_m++; itr_answer++; } if( p_m == nullptr ){ memory_n.push_front( n ); memory_m.push_front( VLArray<INT>() ); memory_answer.push_front( VLArray<INT>() ); p_m = &( memory_m.front() ); p_answer = &( memory_answer.front() ); } const INT size = p_m->size(); // p_mには{...,3,2,1}と入っていくのでm <= sizeの時にmが見付かる。 if( m <= size ){ auto itr_m_current = p_m->begin() , end_m_current = p_m->end(); auto itr_answer_current = p_answer->begin(); while( itr_m_current != end_m_current ){ if( *itr_m_current == m ){ return *itr_answer_current; } itr_m_current++; itr_answer_current++; } } const INT answer = ( CombinationNormalMethod<INT>( n , m - 1 ) * ( n - m + 1 ) ) / m; p_m->push_front( m ); p_answer->push_front( answer ); return p_answer->front(); } template <typename INT> INT CombinationLoopMethod( const INT& n , const INT& m ) { const INT m_comp = n - m; const INT m_copy = m_comp < m ? m_comp : m; INT answer = 1; for( INT i = 0 ; i < m_copy ; i++ ){ answer *= ( n - i ); answer /= i + 1; } return answer; } template <typename INT> inline INT CombinationFactorialNormalMethod( const INT& n , const INT& m ) { return Factorial<INT>( n , n - m + 1 , "normal" ) / Factorial<INT>( m , 1 , "normal" ); } template <typename INT> inline INT CombinationFactorialLoopMethod( const INT& n , const INT& m ) { return Factorial<INT>( n , n - m + 1 , "loop" ) / Factorial<INT>( m , 1 , "loop" ); } template <typename INT> inline INT CombinationModularFactorialInverseNormalMethod( const INT& n , const INT& m ) { return Factorial<INT>( n , n - m + 1 , "normal" ) * ModularFactorialInverse<INT,INT>( m , 1 , "normal" ); } template <typename INT> inline INT CombinationModularFactorialInverseLoopMethod( const INT& n , const INT& m ) { return Factorial<INT>( n , n - m + 1 , "loop" ) * ModularFactorialInverse<INT,INT>( m , 1 , "loop" ); } template <typename T> using Matrix_Body = VLArray<VLArray<T> >; using SizeTypeForMatrix = ll; template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> class Matrix { private: Matrix_Body<T> m_M; public: // argsの長さがXYでなくてもコンパイルエラーとならないがサポート外である。 template <typename... Args> Matrix( const Args&... args ) noexcept; inline Matrix( const Matrix<X,Y,T>& mat ) noexcept; // ( X , Y )行列でないものも引数に取れるがサポート外である。 template <typename... Args> inline Matrix( const Matrix_Body<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 Matrix_Body<T>& GetMatrixBody() noexcept; inline const Matrix_Body<T>& GetMatrixBody() const noexcept; static inline const Matrix<Y,X,T>& Unit() noexcept; private: static inline void ConstructMatrixBody( Matrix_Body<T>& M , VLArray<T>& vec ) noexcept; template <typename Arg , typename... Args> static void ConstructMatrixBody( Matrix_Body<T>& M , VLArray<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 ); template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> template <typename... Args> Matrix<Y,X,T>::Matrix( const Args&... args ) noexcept : m_M() { Matrix_Body<T> M{}; VLArray<T> vec{}; ConstructMatrixBody( M , vec , args... ); m_M = M; } template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> inline Matrix<Y,X,T>::Matrix( const Matrix<X,Y,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 Matrix_Body<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 Matrix_Body<T>& Matrix<Y,X,T>::GetMatrixBody() noexcept { return m_M; } template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> inline const Matrix_Body<T>& Matrix<Y,X,T>::GetMatrixBody() 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 { Matrix_Body<T> M{}; for( SizeTypeForMatrix y = 0 ; y < Y ; y++ ){ VLArray<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>::ConstructMatrixBody( Matrix_Body<T>& M , VLArray<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>::ConstructMatrixBody( Matrix_Body<T>& M , VLArray<T>& vec , const Arg& arg , const Args&... args ) noexcept { vec.push_back( arg ); if( vec.size() == X ){ ConstructMatrixBody( M , vec ); } if( M.size() < Y ){ ConstructMatrixBody( 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.GetatrixBody() == mat2.GetMatrixBody(); } 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 Matrix<Z,X,T> mat2_t = Transpose( mat2 ); const Matrix_Body<T>& M1 = mat1.GetMatrixBody(); const Matrix_Body<T>& M2 = mat2_t.GetMatrixBody(); Matrix_Body<T> M_prod{}; for( auto itr1y = M1.begin() , end1y = M1.end() ; itr1y != end1y ; itr1y++ ){ VLArray<T> vec{}; for( auto itr2z = M2.begin() , end2z = M2.end() ; itr2z != end2z ; itr2z++ ){ auto itr1yx = itr1y->begin() , end1yx = itr1y->end() , itr2xz = itr2z->begin(); T inner_product = 0; while( itr1yx != end1yx ){ inner_product += ( *itr1yx ) * ( *itr2xz ); itr1yx++; itr2xz++; } 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 Matrix_Body<T>& M = mat.GetMatrixBody(); Matrix_Body<T> M_t{}; auto beginy = M.begin(); for( auto itr1x = beginy->begin() , end1x = beginy->end() ; itr1x != end1x ; itr1x++ ){ M_t.push_back( VLArray<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 Matrix_Body<T>& M = mat.GetMatrixBody(); for( auto itry = M.begin() , endy = M.end() ; itry != endy ; itry++ ){ auto itrxy = itry->begin(); for( int j = 0 ; j < i ; j++ ){ itrxy++; } answer += *itrxy; i++; } return answer; } MOD Solution( const MOD& N , const ll& M , const MOD& K ); int main() { ll N; ll M; ll K; // N = 1; // M = 478133453679163179; // K = 194021; cin >> N; cin >> M; cin >> K; if( N * M < K ){ cout << 0 << endl; } else { cout << Solution( MOD( N ) , M , MOD( K ) ).Represent() << endl; } return 0; } MOD A1( const ll& M , const MOD& K ); MOD A2( const ll& M , const MOD& K ); MOD A3( const ll& M , const MOD& K ); MOD Solution( const MOD& N , const ll& M , const MOD& K ) { if( N == 1 ){ return A1( M , K ); } if( N == 2 ){ return A2( M , K ); } return A3( M , K ); } MOD A1( const ll& M , const MOD& K ) { // sum( int k = 0 ; true ; k++ ) C( K , k ) * A1( M , k ) // = sum( int k = 0 ; k <= K ; k++ ) C( K , k ) * A1( M , k ) // = K * ( K - 1 ) ^ ( M - 1 ) // A1( M , K ) = MahlerExpansion( X * ( X - 1 ) ^ ( M - 1 ) , K ) // = Difference ^ K ( X * ( X - 1 ) ^ ( M - 1 ) )( 0 ) // = ( sum( k = 0 ; k <= K ; k++ ) ( -1 ) ^ ( K - k ) * C( K , k ) * ( X * ( X - 1 ) ^ ( M - 1 ) )( X + k ) )( 0 ) // = sum( k = 0 ; k <= K ; k++ ) ( -1 ) ^ ( K - k ) * C( K , k ) * ( ( X + k ) * ( X + k - 1 ) ^ ( M - 1 ) )( 0 ) // = sum( k = 0 ; k <= K ; k++ ) ( -1 ) ^ ( K - k ) * C( K , k ) * k * ( k - 1 ) ^ ( M - 1 ) // = ( -1 ) ^ K * sum( k = 0 ; k <= K ; k++ ) ( -1 ) ^ k * C( K , k ) * k * ( k - 1 ) ^ ( M - 1 ) // = ( -1 ) ^ ( K + 1 ) * sum( k = 0 ; k < K ; k++ ) ( -1 ) ^ k * C( K , k + 1 ) * ( k + 1 ) * k ^ ( M - 1 ) // = ( -1 ) ^ ( K + 1 ) * K * sum( k = 0 ; k < K ; k++ ) ( -1 ) ^ k * C( K - 1 , k ) * k ^ ( M - 1 ) MOD answer = 0; const MOD K_decr = K - 1; const ll& K_decr_rep = K_decr.Represent(); const ll M_decr = ( M - 1 ) % ( PRIME_NUMBER - 1 ); const string mode_comb = "normal"; const string mode_pow = "binary"; for( ll k = 0 ; k <= K_decr_rep ; k++ ){ const MOD d = Combination<MOD>( K_decr , k , mode_comb ) * Power<MOD,ll>( k , M_decr , 1 , true , mode_pow ); if( k % 2 == 0 ){ answer += d; } else { answer -= d; } } answer *= K; if( K_decr_rep % 2 == 1 ){ answer *= -1; } return answer; } MOD A2( const ll& M , const MOD& K ) { // sum( int k = 0 ; true ; k++ ) C( K , k ) * A2( M , k ) // = sum( int k = 0 ; k <= K ; k++ ) C( K , k ) * A2( M , k ) // = K * ( K - 1 ) * ( 1 * ( K - 1 ) + ( K - 2 ) ^ 2 ) ^ ( M - 1 ) // = K * ( K - 1 ) * ( K ^ 2 - 3 * K + 3 ) ^ ( M - 1 ) // A2( M , K ) // = MahlerExpansion( X * ( X - 1 ) * ( X ^ 2 - 3 * X + 3 ) ^ ( M - 1 ) , K ) // = Difference ^ K ( X * ( X - 1 ) * ( X ^ 2 - 3 * X + 3 ) ^ ( M - 1 ) )( 0 ) // = sum( int k = 0 ; k <= K ; k++ ) ( -1 ) ^ ( K - k ) * // C( K , k ) * k * ( k - 1 ) * ( k ^ 2 - 3 * k + 3 ) ^ ( M - 1 ) // = ( -1 ) ^ K * K * ( K - 1 ) * sum( int k = 2 ; k <= K ; k++ ) // ( -1 ) ^ k * C( K - 2 , k - 2 ) * ( k ^ 2 - 3 * k + 3 ) ^ ( M - 1 ) // = ( -1 ) ^ K * K * ( K - 1 ) * sum( int k = 0 ; k <= K - 2 ; k++ ) // ( -1 ) ^ k * C( K - 2 , k ) * ( k ^ 2 + k + 1 ) ^ ( M - 1 ) MOD answer = 0; const MOD K_decr2 = K - 2; const ll& K_decr2_rep = K_decr2.Represent(); const ll M_decr = ( M - 1 ) % ( PRIME_NUMBER - 1 ); const string mode_comb = "normal"; const string mode_pow = "binary"; for( ll k = 0 ; k <= K_decr2_rep ; k++ ){ const MOD k_copy = k; const MOD d = Combination<MOD>( K_decr2 , k_copy , mode_comb ) * Power<MOD,ll>( k_copy * k_copy + k_copy + 1 , M_decr , 1 , true , mode_pow ); if( k % 2 == 0 ){ answer += d; } else { answer -= d; } } answer *= K * ( K - 1 ); if( K_decr2_rep % 2 == 1 ){ answer *= -1; } return answer; } MOD A3( const ll& M , const MOD& K ) { // XYX -> X'Y'X'パターン // 1 * ( K - 1 ) + ( K - 2 ) ^ 2 // = K ^ 2 - 3 * K + 3 // XYX -> X'Y'Z'パターン // 1 * ( 1 * ( K - 2 ) + ( K - 2 ) * ( K - 3 ) ) + ( K - 2 ) * ( 1 * ( K - 2 ) + ( K - 3 ) ^ 2 ) // = ( K - 2 ) ^ 2 + ( K - 2 ) * ( ( K - 2 ) + ( K - 3 ) ^ 2 ) // = ( K - 2 ) * ( K ^ 2 - 4 * K + 5 ) // = K ^ 3 - 6 * K ^ 2 + 13 * K - 10 // XYXパターン合計 // ( K ^ 2 - 3 * K + 3 ) + ( K ^ 3 - 6 * K ^ 2 + 13 * K - 10 ) // = K ^ 3 - 5 * K ^ 2 + 10 * K - 7 // XYZ -> X'Y'X'パターン // 1 * ( K - 1 ) + ( K - 3 ) * ( K - 2 ) // = K ^ 2 - 4 * K + 5 // XYZ -> X'Y'Z'パターン // 1 * ( 1 * ( K - 2 ) + ( K - 2 ) * ( K - 3 ) ) + 1 * ( K - 2 ) ^ 2 + ( K - 3 ) * ( 1 * ( K - 2 ) + ( K - 3 ) ^ 2 ) // = ( K - 2 ) ^ 2 + ( K - 2 ) ^ 2 + ( K - 3 ) * ( ( K - 2 ) + ( K - 3 ) ^ 2 ) // = 2 * ( K - 2 ) ^ 2 + ( K - 3 ) * ( K ^ 2 - 5 * K + 7 ) // = 2 * ( K - 2 ) ^ 2 + K ^ 3 - 8 * K ^ 2 + 22 * K - 21 // = K ^ 3 - 6 * K ^ 2 + 14 * K - 13 // XYZパターン合計 // ( K ^ 2 - 4 * K + 5 ) + ( K ^ 3 - 6 * K ^ 2 + 14 * K - 13 ) // = K ^ 3 - 5 * K ^ 2 + 10 * K - 8 // Transfer( X ) // = Matrix<2,2>( // X ^ 2 - 3 * X + 3 , X ^ 2 - 4 * X + 5 , // X ^ 3 - 6 * X ^ 2 + 13 * X - 10 , X ^ 3 - 6 * X ^ 2 + 14 * X - 13 // ) // sum( int k = 0 ; true ; k++ ) C( K , k ) * A3( M , k ) // = sum( int k = 0 ; k <= K ; k++ ) C( K , k ) * A3( M , k ) // = Trace( // Matrix<1,2>( 1 , 1 ) * Transfer( K ) ^ ( M - 1 ) // * Matrix<2,1>( K * ( K - 1 ) , K * ( K - 1 ) * ( K - 2 ) ) // ) // A3( M , K ) // = MahlerExpansion( // Trace( // Matrix<1,2>( 1 , 1 ) * Transfer( X ) ^ ( M - 1 ) // * Matrix<2,1>( X * ( X - 1 ) , X * ( X - 1 ) * ( X - 2 ) ) // ) , // K // ) // = Difference ^ K ( // Trace( // Matrix<1,2>( 1 , 1 ) * Transfer( X ) ^ ( M - 1 ) // * Matrix<2,1>( X * ( X - 1 ) , X * ( X - 1 ) * ( X - 2 ) ) // ) // )( 0 ) // = sum( int k = 0 ; k <= K ; k++ ) ( -1 ) ^ ( K - k ) * C( K , k ) // * Trace( // Matrix<1,2>( 1 , 1 ) * Transfer( k ) ^ ( M - 1 ) // * Matrix<2,1>( k * ( k - 1 ) , k * ( k - 1 ) * ( k - 2 ) ) // ) // = ( -1 ) ^ K * Trace( Matrix<1,2>( 1 , 1 ) // * sum( int k = 0 ; k <= K ; k++ ) ( -1 ) ^ k * C( K , k ) * Transfer( k ) ^ ( M - 1 ) * Matrix<2,1>( k * ( k - 1 ) , k * ( k - 1 ) * ( k - 2 ) ) // ) Matrix<2,1,MOD> answer{ 0 , 0 }; const ll& K_rep = K.Represent(); const ll M_decr = M - 1; const string mode_comb = "normal"; const string mode_pow = "binary"; for( ll k = 0 ; k <= K_rep ; k++ ){ const MOD k_copy = k; const MOD k2 = k * k; const MOD k3 = k2 * k; Matrix<2,2,MOD> Transfer{ k2 - 3 * k + 3 , k2 - 4 * k + 5 , k3 - 6 * k2 + 13 * k - 10 , k3 - 6 * k2 + 14 * k - 13 }; const MOD d1 = Combination<MOD>( K , k_copy , mode_comb ); const Matrix<2,2,MOD> d2 = Power<Matrix<2,2,MOD>,ll>( Transfer , M_decr , Matrix<2,2,MOD>::Unit() , true , mode_pow ); const Matrix<2,1,MOD> d3{ k * ( k - 1 ) , k * ( k - 1 ) * ( k - 2 ) }; const Matrix<2,1,MOD> d = d1 * d2 * d3; if( k % 2 == 0 ){ answer += d; } else { answer -= d; } } if( K_rep % 2 == 1 ){ answer *= -1; } return Trace<1,MOD>( Matrix<1,2,MOD>( 1 , 1 ) * answer ); }