結果
| 問題 | No.2183 LCA on Rational Tree |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2023-06-24 21:07:59 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 107 ms / 2,000 ms |
| コード長 | 36,583 bytes |
| コンパイル時間 | 19,700 ms |
| コンパイル使用メモリ | 275,624 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-07-02 00:07:39 |
| 合計ジャッジ時間 | 20,727 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 107 ms
5,248 KB |
| testcase_02 | AC | 86 ms
5,376 KB |
| testcase_03 | AC | 34 ms
5,376 KB |
| testcase_04 | AC | 11 ms
5,376 KB |
| testcase_05 | AC | 46 ms
5,376 KB |
ソースコード
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ); signal( SIGABRT , &AlertAbort )
#define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE )
#define CERR( ANSWER ) cerr << ANSWER << endl;
#define COUT( ANSWER ) cout << ANSWER << endl
#define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック； " << ( MIN ) << ( ( MIN ) <= A ? "<=" : ">" ) << A << ( A <= ( MAX ) ? "<=" : ">" ) << ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) )
#define LIBRARY_SEARCH if( LibrarySearch() != 0 ){ QUIT; };
#else
#pragma GCC optimize ( "O3" )
#pragma GCC optimize( "unroll-loops" )
#pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )
#define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE )
#define CERR( ANSWER )
#define COUT( ANSWER ) cout << ANSWER << "\n"
#define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
#define LIBRARY_SEARCH
#endif
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#define ATT __attribute__( ( target( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) ) )
#define TYPE_OF( VAR ) decay_t<decltype( VAR )>
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#define CIN( LL , A ) LL A; cin >> A
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX )
#define SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX )
#define GETLINE( A ) string A; getline( cin , A )
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR )
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ )
#define FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; VAR -- )
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES )
#define QUIT return 0
#define RETURN( ANSWER ) COUT( ( ANSWER ) ); QUIT
#define SET_PRECISION( PRECISION ) cout << fixed << setprecision( PRECISION )
inline void AlertAbort( int n ) { cerr << "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" << endl; }
template <typename T> inline T Absolute( const T& a ){ return a > 0 ? a : -a; }
template <typename T> inline T Residue( const T& a , const T& p ){ return a >= 0 ? a % p : ( a % p ) + p; }
#define POWER( ANSWER , ARGUMENT , EXPONENT ) \
static_assert( ! is_same<TYPE_OF( ARGUMENT ),int>::value && ! is_same<TYPE_OF( ARGUMENT ),uint>::value ); \
TYPE_OF( ARGUMENT ) ANSWER{ 1 }; \
{ \
TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT ); \
TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \
while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \
if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \
ANSWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \
} \
ARGUMENT_FOR_SQUARE_FOR_POWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \
EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \
} \
} \
#define POWER_MOD( ANSWER , ARGUMENT , EXPONENT , MODULO ) \
ll ANSWER{ 1 }; \
{ \
ll ARGUMENT_FOR_SQUARE_FOR_POWER = ( MODULO + ( ( ARGUMENT ) % MODULO ) ) % MODULO; \
TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \
while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \
if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \
ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \
} \
ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \
EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \
} \
} \
#define FACTORIAL_MOD( ANSWER , ANSWER_INV , INVERSE , MAX_INDEX , CONSTEXPR_LENGTH , MODULO ) \
static ll ANSWER[CONSTEXPR_LENGTH]; \
static ll ANSWER_INV[CONSTEXPR_LENGTH]; \
static ll INVERSE[CONSTEXPR_LENGTH]; \
{ \
ll VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \
ANSWER[0] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL; \
FOREQ( i , 1 , MAX_INDEX ){ \
ANSWER[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= i ) %= MODULO; \
} \
ANSWER_INV[0] = ANSWER_INV[1] = INVERSE[1] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \
FOREQ( i , 2 , MAX_INDEX ){ \
ANSWER_INV[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= INVERSE[i] = MODULO - ( ( ( MODULO / i ) * INVERSE[MODULO % i] ) % MODULO ) ) %= MODULO; \
} \
} \
// 二分探索テンプレート
// EXPRESSIONがANSWERの広義単調関数の時、EXPRESSION >= TARGETの整数解を格納。
#define BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET , INEQUALITY , UPDATE_U , UPDATE_L , UPDATE_ANSWER ) \
static_assert( ! is_same<TYPE_OF( TARGET ),uint>::value && ! is_same<TYPE_OF( TARGET ),ull>::value ); \
ll ANSWER = MINIMUM; \
if( MINIMUM <= MAXIMUM ){ \
ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \
ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM; \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH; \
while( VARIABLE_FOR_BINARY_SEARCH_L != VARIABLE_FOR_BINARY_SEARCH_U ){ \
VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \
CERR( "二分探索中： " << VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" << TARGET << "=" << VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH INEQUALITY 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_U = UPDATE_U; \
} else { \
VARIABLE_FOR_BINARY_SEARCH_L = UPDATE_L; \
} \
ANSWER = UPDATE_ANSWER; \
} \
CERR( "二分探索終了： " << VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" << TARGET << ( EXPRESSION > TARGET ? ">0" : EXPRESSION < TARGET ? "<0" : "0" ) ); \
} else { \
CERR( "二分探索失敗： " << MINIMUM << ">" << MAXIMUM << "です。" ); \
} \
// 単調増加の時にEXPRESSION >= TARGETの最小解を格納。
#define BS1( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET , >= , ANSWER , ANSWER + 1 , ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \
// 単調増加の時にEXPRESSION <= TARGETの最大解を格納。
#define BS2( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET , > , ANSWER - 1 , ANSWER , ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \
// 単調減少の時にEXPRESSION >= TARGETの最大解を格納。
#define BS3( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET , < , ANSWER - 1 , ANSWER , ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \
// 単調減少の時にEXPRESSION <= TARGETの最小解を格納。
#define BS4( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET , <= , ANSWER , ANSWER + 1 , ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \
// 圧縮用
#define TE template
#define TY typename
#define US using
#define ST static
#define IN inline
#define CL class
#define PU public
#define OP operator
#define CE constexpr
#define CO const
#define NE noexcept
#define RE return
#define WH while
#define VO void
#define VE vector
#define LI list
#define BE begin
#define EN end
#define SZ size
#define MO move
#define TH this
#define CRI CO int&
#define CRUI CO uint&
#define CRL CO ll&
int QuitLibrarySearch( const int& problems_size ){
cerr << "返答は" << problems_size - 1 << "以下の非負整数にしてください。";
CERR( "終了します。" );
CERR( "" );
return -1;
}
int LibrarySearch( int num = -1 )
{
vector<string> problems =
{
"数に関する問題。" ,
"配列に関する問題。" ,
"文字列に関する問題。" ,
"順列に関する問題。" ,
"矩形領域に関する問題。" ,
"グラフに関する問題。" ,
"部分和問題。" ,
"確率／期待値に関する問題。" ,
"ゲームに関する問題。" ,
"論理に関する問題。" ,
"順序に関する問題。" ,
"関数適用に関する問題。" ,
"構築問題。"
};
CEXPR( int , num_graph , 5 );
CEXPR( int , num_subsequence_sum , 6 );
CEXPR( int , num_game , 8 );
int problems_size = problems.size();
string reply{};
if( num == -1 ){
CERR( "ライブラリーを探索しますか？[y/n]" );
CIN( string , reply );
if( reply == "n" ){
CERR( "ライブラリーを探索せずに続行します。" );
CERR( "" );
return 0;
} else if( reply != "y" ){
CERR( "y/nのいずれかで答えてください。" );
CERR( "終了します。" );
CERR( "" );
return -1;
}
CERR( "" );
CERR( "ライブラリーを探索します。" );
CERR( "問題の種類を番号で指定してください；" );
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
cin >> num;
}
CERR( "" );
int num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "入力は１つの数か、１つの数と法を表す数ですか？[y/n/c]" );
cin >> reply;
CERR( "" );
if( reply == "y" ){
CERR( "まずは小さい入力の場合を愚直に計算し、OEISで検索しましょう。" );
CERR( "https://oeis.org/?language=japanese" );
CERR( "" );
CERR( "次に出力の定義と等価な式を考察しましょう。" );
CERR( "- 単調ならば、冪乗や階乗" );
CERR( "- 定義にp進法が使われていれば、各種探索アルゴリズム" );
CERR( "- 入力が素数に近い場合に規則性があれば、p進付値、p進法、" );
CERR( " オイラー関数、約数の個数など" );
CERR( "を検討しましょう。" );
} else if( reply == "n" ){
CERR( "このケースのライブラリー探索は未実装です。" );
} else {
CERR( "y/nのいずれかで答えてください。" );
CERR( "終了します。" );
CERR( "" );
return -1;
}
CERR( "" );
CERR( "マルチテストケースの場合は以下の前計算を検討しましょう；" );
CERR( "素数列挙、約数列挙、サブゴールとなる関係式を満たす解列挙。" );
} else if( num == num_temp++ ){
CERR( "より詳細な問題の種類を番号で指定してください；" );
problems =
{
"区間処理問題。" ,
"最大化問題。" ,
"最長部分列問題。" ,
"数え上げ問題。" ,
"部分和問題。"
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "使用する代数構造を番号で指定してください；" );
problems =
{
"可換群構造+" ,
"可換羃等モノイド構造∨" ,
"モノイド構造*" ,
"非結合的マグマ構造*" ,
"集合へのマグマ作用(*,\\cdot)" ,
"モノイドへのマグマ作用(+,\\cdot)" ,
"定数とのmaxを取った値の区間和取得"
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "- 区間加算／区間取得が必要ならば可換群BIT" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT\\Template" );
CERR( "- 一点代入／一点加算／区間取得が必要ならば可換群平方分割" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template" );
CERR( "- 区間以外の領域で加算／全更新後の一点取得が必要ならば階差数列" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\Tree\\DifferenceSeqeuence" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "- 一点代入／区間加算／一点取得／区間取得が必要ならば可換羃等モノイドBIT" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT\\IntervalMax\\Template" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "- 一点代入／区間取得が必要ならばモノイドBIT" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT\\Template\\Monoid" );
CERR( "- 一点加算／区間加算／一点取得／区間取得が必要ならばモノイド平方分割" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template\\Monoid" );
CERR( "- 一点代入／一点取得／区間取得が必要ならばモノイドセグメント木" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SegmentTree" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "- 写像のコード化" );
CERR( " \\Mathematics\\Function\\Encoder" );
CERR( "によりモノイドに帰着させることを検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "- 一点作用／区間作用／一点取得が必要ならば双対平方分割" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template\\Dual" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "- 区間代入／区間作用／区間加算／一点取得／区間取得が必要な場合は遅延評価平方分割" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template\\LazyEvaluation" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "maxで全体更新でなく区間更新をする場合の汎用的な解法は分かりません。" );
CERR( "例えば区間が包含について単調でmaxを取る値も単調であれば全体更新と" );
CERR( "同様の処理ができます。状況に応じた考察をしましょう。" );
CERR( "" );
CERR( "maxで全体更新をする場合、maxを取る値は単調である場合に帰着できます。" );
CERR( "maxで全体更新をしない場合、つまりただmaxの区間和を処理するだけの場合、" );
CERR( "クエリの順番を入れ替えることができるので、単調な全体更新に帰着できます。" );
CERR( "従って以下では単調な全体更新の問題を考えます。" );
CERR( "" );
CERR( "maxを取る定数を変数化し、元の値との大小を表す{0,1}値の係数を考えます。" );
CERR( "すると区間作用前後の値は統一的にその係数と変数を使って表せます。" );
CERR( "配列の各成分の係数の値が変化するイベントとクエリをソートして管理し、" );
CERR( "クエリがイベントを跨ぐたびに係数を更新することを検討しましょう。" );
CERR( "" );
CERR( "例えばクエリB_qに対するmax(A_i,B_q)の区間和は、" );
CERR( "- 優先度つきキューA'={(A_i,i)|i}（構築O(N log N)）" );
CERR( "- (B_q,q)_qをソートしたB'（構築O(Q log Q)）" );
CERR( "- 長さNの数列C=(0,...,0)（構築O(N)）" );
CERR( "を用意し、B'を前から探索して順に各クエリ(B_q,q)を処理します。" );
CERR( "具体的にはA'を前から探索して順にA_i<B_qとなる各iに対し" );
CERR( "- A'から(A_i,i)を削除（クエリ合計O(N)）" );
CERR( "- A_iを0に更新（クエリ合計O(N log N)）" );
CERR( "- C_iを1に更新（各クエリO(log N)）" );
CERR( "- A+C×B_qの区間和取得（各クエリO(log N)）" );
CERR( "とすれば合計O((N + Q)log N + Q log Q)で処理できます。" );
}
} else if( num == num_temp++ ){
CERR( "最大化すべき式のサブゴールfに表れる項xのうち決め打ちやすいものを探しましょう。" );
CERR( "- 配列の長さをiで打ち切った時のxの候補数をX(i)" );
CERR( "- 配列の長さをiで打ち切ってxを決め打った時の配列の長さi+1でのxの候補数をdX(i)" );
CERR( "と置きます。" );
CERR( "- O(sum_i X(i) dX(i))が通りそうでfがxからO(1)で計算できるならば、iとxに関する動的計画法" );
CERR( "- O(N log_2 X)が通りそうでfがxからO(N)で計算できxに関して単調ならば、xの二分探索" );
CERR( "- O(N log_2 N)が通りそうでxを上手く並び替えるとfがxからO(log_2 N)で計算できるならば、" );
CERR( " 優先度つきキューなどでのxの管理" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "全順序か疎な半順序かで効率的な実装が違います。" );
CERR( "- 全順序ならば、条件を満たす部分列の長さの最大値をインデックスに持つ配列を用いて、" );
CERR( " それらの部分列の末尾である項を記録すること" );
CERR( "- 疎な半順序ならば、条件を満たす部分列の末尾をインデックスに持つ連想配列を用いて、" );
CERR( " それら部分列の長さの最大値を記録すること" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "gcdやmaxなどの羃等演算に関する等式を指定した数え上げは不等式の方が" );
CERR( "扱いやすいのでゼータ変換／メビウス変換を検討しましょう。" );
} else if( num == num_temp++ ){
return LibrarySearch( num = num_subsequence_sum );
}
} else if( num == num_temp++ ){
CERR( "より詳細な問題の種類を番号で指定してください；" );
problems =
{
"部分列マッチング問題。" ,
"回文探索問題。"
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "基本的には丁寧にループを回して解きましょう。" );
CERR( "- 比較対象が少ない場合、前または後ろから順に探索（貪欲法／動的計画法）" );
CERR( "- ワイルドカードを含む場合、" );
CERR( " - 前または後ろから順に場合分けをしてO(N)で処理できるか" );
CERR( " - 可能な代入方法を絞り込んでO(N)種類に落せるか" );
CERR( "- 比較回数が多い場合、ローリングハッシュ" );
CERR( "- マッチングする文字列の最長化をする場合、Zアルゴリズム" );
CERR( " https://qiita.com/Pro_ktmr/items/16904c9570aa0953bf05" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "回文判定は長さに関して再帰的に計算できます。" );
CERR( "- O(N^2)が通る場合、愚直な再帰により前計算で全ての部分列の回文判定" );
CERR( "- O(N^2)が通らない場合、Manacherのアルゴリズムやローリングハッシュで前計算" );
CERR( " https://snuke.hatenablog.com/entry/2014/12/02/235837" );
CERR( "を検討しましょう。" );
}
} else if( num == num_temp++ ){
CERR( "符号の計算は転倒数の計算に帰着させましょう。" );
CERR( "符号と何かの積の和は行列式に帰着させましょう。" );
CERR( "- 行列式そのものなら行基本変形でO(N^3)" );
CERR( "- 余因子展開の途中の値はメモ化再帰でO(N 2^N)" );
CERR( "で計算できます。" );
CERR( "" );
CERR( "１つの順列の転倒数は、" );
CERR( "- O(N^2)が通りそうならば愚直な二重ループ" );
CERR( "- O(N log_2 N)が通りそうならば可換群に対するBIT" );
CERR( " \\Mathematics\\Combinatorial\\Permutation" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT" );
CERR( "で計算しましょう。" );
CERR( "" );
CERR( "条件を満たす順列全体をわたる転倒数の総和は、" );
CERR( "各i<jごとにそこで転倒が生じる順列の個数を計算し、その総和を取りましょう。" );
CERR( "条件が良ければ、転倒が生じる順列の個数は転倒が生じるとは限らない順列の個数の" );
CERR( "半分となります。" );
} else if( num == num_temp++ ){
CERR( "より詳細な問題の種類を番号で指定してください；" );
problems =
{
"探索問題。" ,
"絶対値の最小／最大化問題。" ,
"その他の最小／最大化問題。"
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "隣接関係の定める無向グラフの問題に帰着させましょう。" );
return LibrarySearch( num = num_graph );
} else if( num == num_temp++ ){
CERR( "符号を用いて絶対値を外しましょう。" );
CERR( "- 単調な式に帰着できる場合、二分探索を検討しましょう。" );
CERR( "- 最大化問題の場合、符号パターンの全探策を検討しましょう。" );
CERR( "- マンハッタン距離などは一次変換で簡単にすることを検討しましょう。" );
CERR( "複数のパラメータを決定すべき場合は、サブゴールの式の値を決め打ちましょう。" );
} else if( num == num_temp++ ){
CERR( "このケースのライブラリー探索は不完全です。" );
CERR( "- O(HW)が通りそうならば動的計画法" );
CERR( "- O(HW)が通らなさそうならば見方を変えて最短経路問題に帰着できないか" );
CERR( "を検討しましょう。" );
CERR( "" );
CERR( "例えば迷路の攻略可能性は" );
CERR( "- スタートとゴールが同一の弧状連結成分に属すこと" );
CERR( "- スタートとゴールを分断する壁のパスの非存在性" );
CERR( "などから翻訳できます。" );
}
} else if( num == num_temp++ ){
CERR( "より詳細な問題の種類を番号で指定してください；" );
problems =
{
"２点最短径路（迷路）問題。" ,
"多点最短経路（スタンプラリー）問題。" ,
"木の問題。" ,
"連結性問題。"
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "特定の経路を進むと思い込んで考察漏れをする可能性があります。" );
CERR( "なるべく全ての経路を許した探索アルゴリズムを適用した方が無難です。" );
CERR( "- 特定の２点のみを考える場合、BFSやDijkstra" );
CERR( " \\Utility\\Search\\BreadthFirst" );
CERR( " \\Utility\\Search\\Dijkstra" );
CERR( "- 全ての２点の組み合わせを考える場合、" );
CERR( " - 一般のモノイド演算を考えておりO(V^3)が通りそうならば、FloydWarshall" );
CERR( " \\Utility\\Search\\FloydWarshall" );
CERR( " - max演算を考えておりO(E(log_2 E + α(V)))が通りそうならば、UnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "HeldKarpや、移動方法を分類するパラメータの全探策などを検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "深さ優先探索や動的木を検討しましょう。" );
CERR( "\\Utility\\Search\\DepthFirst" );
CERR( "\\Utility\\VLTree" );
} else if( num == num_temp++ ){
CERR( "- 0次の連結性はUnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "- 高次の連結性は深さ優先探索" );
CERR( " \\Utility\\Search\\DepthFirst" );
CERR( "- マルチテストケースの場合は座標圧縮との併用" );
CERR( "を検討しましょう。" );
}
} else if( num == num_temp++ ){
CERR( "より詳細な問題の種類を番号で指定してください；" );
problems =
{
"部分和の最大化問題。" ,
"部分和の数え上げ問題。"
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "項数N、重みの総和の上限W（多変数も可）、価値（和を取る値）の上限Vとします。" );
CERR( "- B=∞ならば、通常のナップサック問題と同様の動的計画法" );
CERR( "- B<∞でO(2^N)が通りそうならば愚直に全探策" );
CERR( "- B<∞でO(2^{N/2} N)が通りそうならば半分全列挙" );
CERR( "- B<∞で重みと価値が等しくO(NV)が通りそうならば[B-V,B+V]での実現可能性を" );
CERR( " 遷移する動的計画法" );
CERR( " https://stackoverflow.com/a/18949218" );
CERR( "- Wが10^5オーダーで重みと価値が等しくO((N+W)log_2 W)が通りそうならば" );
CERR( " 適当な法での畳み込み（確率的解法）" );
CERR( " \\Mathematics\\Polynomial" );
} else if( num == num_temp++ ){
CERR( "項数N、重みの総和の上限Wとします。" );
CERR( "- 重みと価値が異なりO(2^N)が通りそうならば愚直な２変数多項式乗算" );
CERR( "- 重みと価値が等しくO(2^N)が通りそうならば愚直な１変数多項式乗算" );
CERR( "- 重みと価値が等しくO(2^{N/2}N)が通りそうならば半分ずつ多項式乗算を" );
CERR( " して最後にそれらの積の１係数のみの計算" );
CERR( "- 重みと価値が等しくWが10^5オーダーで法が与えられていてO((N+W)log_2 W)が" );
CERR( " 通りそうならば畳み込み" );
CERR( " \\Mathematics\\Polynomial" );
}
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "確率計算は" );
CERR( "- 余事象や包除原理（高速ゼータ変換）" );
CERR( "- 同様に確からしい事象の特定" );
CERR( "- ベイズの定理" );
CERR( "を検討しましょう。" );
CERR( "" );
CERR( "期待値計算は" );
CERR( "- 上記方法での確率計算" );
CERR( "- 対象を独立な和で表して線形性" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "ゲームの和に分解できる場合は最小単位で考察をし、グランディ数を実装しましょう。" );
CERR( "これ以上分解できないゲームには整礎構造を探し、順序数の小さい順に実験をしましょう。" );
} else if( num == num_temp++ ){
CERR( "複数の命題に対する" );
CERR( "- 区間処理は各種代数的データ構造" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace" );
CERR( "- 充足可能性判定は頂点数を２倍してUnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "より詳細な問題の種類を番号で指定してください；" );
problems =
{
"半順序集合上の関数の計算問題。" ,
"半順序集合上の降下／上昇列に関する問題。"
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "ゼータ変換を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "順序関係の定める有向グラフの問題に帰着させましょう。" );
return LibrarySearch( num = num_graph );
}
} else if( num == num_temp++ ){
CERR( "より詳細な問題の種類を番号で指定してください；" );
problems =
{
"反復合成の計算問題。" ,
"反復合成による到達可能性問題。"
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "定義域の要素数N、テストケース数T、反復回数の上限Kとします。" );
CERR( "- O((N + T)log_2 K)が通りそうならばダブリング" );
CERR( " \\Mathematics\\Function\\Iteration\\Doubling" );
CERR( "- O(TN)が通りそうならばループ検出" );
CERR( " \\Mathematics\\Function\\Iteration\\LoopDetection" );
CERR( "- O(N)すら通らなさそうならば関数の規則性を見付けるための実験" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "関数による遷移が定める有向グラフの問題に帰着させましょう。" );
return LibrarySearch( num = num_graph );
}
} else if( num == num_temp++ ){
CERR( "より詳細な問題の種類を番号で指定してください；" );
problems =
{
"数や配列や文字列の構築。" ,
"経路の構築。" ,
"戦略の構築。"
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "p進法を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "可能な経路の定める無向グラフの問題に帰着させましょう。" );
return LibrarySearch( num = num_graph );
} else if( num == num_temp++ ){
CERR( "ゲームの問題に帰着させましょう。" );
return LibrarySearch( num = num_game );
}
}
CERR( "" );
CERR( "ライブラリー探索は以上です。終了します。" );
CERR( "" );
return -1;
}
template <typename INT>
INT GCD( const INT& b_0 , const INT& b_1 )
{
INT b[2] = { b_0 , b_1 };
int i_0 = ( b_0 >= b_1 ? 0 : 1 );
int i_1 = 1 - i_0;
while( b[i_1] != 0 ){
b[i_0] %= b[i_1];
swap( i_0 , i_1 );
}
return b[i_0];
}
template <typename INT , INT val_limit , int length_max = val_limit>
class PrimeEnumeration
{
public:
INT m_val[length_max];
int m_length;
inline constexpr PrimeEnumeration();
};
template <typename INT , INT val_limit , int length_max>
inline constexpr PrimeEnumeration<INT,val_limit,length_max>::PrimeEnumeration() : m_val() , m_length( 0 )
{
bool is_comp[val_limit] = {};
for( INT i = 2 ; i < val_limit ; i++ ){
if( is_comp[i] == false ){
INT j = i;
while( ( j += i ) < val_limit ){
is_comp[j] = true;
}
m_val[m_length++] = i;
if( m_length >= length_max ){
break;
}
}
}
}
template <typename INT , INT val_limit , int length_max>
void SetPrimeFactorisation( const PrimeEnumeration<INT,val_limit,length_max>& prime , const INT& n , vector<INT>& P , vector<INT>& exponent )
{
INT n_copy = n;
int i = 0;
while( i < prime.m_length ){
const INT& p = prime.m_val[i];
if( p * p > n_copy ){
break;
}
if( n_copy % p == 0 ){
P.push_back( p );
exponent.push_back( 1 );
INT& exponent_back = exponent.back();
n_copy /= p;
while( n_copy % p == 0 ){
exponent_back++;
n_copy /= p;
}
}
i++;
}
if( n_copy != 1 ){
P.push_back( n_copy );
exponent.push_back( 1 );
}
return;
}
template <typename INT , INT val_limit , int length_max>
list<int> EnumerateDivisor( const PrimeEnumeration<INT,val_limit,length_max>& prime , INT n ) noexcept
{
vector<INT> P{};
vector<INT> exponent{};
SetPrimeFactorisation( prime , n , P , exponent );
const int length = P.size();
list<INT> divisor{};
divisor.push_back( 1 );
auto begin = divisor.begin() , end = divisor.end();
for( int i = 0 ; i < length ; i++ ){
const INT& P_i = P[i];
const int& exponent_i = exponent[i];
list<int> temp{};
INT power = 1;
for( int e = 1 ; e <= exponent_i ; e++ ){
power *= P_i;
for( auto itr = begin ; itr != end ; itr++ ){
temp.push_back( *itr * power );
}
}
while( ! temp.empty() ){
divisor.push_back( temp.front() );
temp.pop_front();
}
}
return divisor;
}
int main()
{
UNTIE;
LIBRARY_SEARCH;
CEXPR( int , bound_Q , 3000 );
CIN_ASSERT( Q , 1 , bound_Q );
// CEXPR( int , bound_T , 100000 );
// CIN_ASSERT( T , 1 , bound_T );
// CEXPR( int , bound_N , 100000 ); // 0が5個
// // CEXPR( ll , bound_N , 1000000000 ); // 0が9個
// // CEXPR( ll , bound_N , 1000000000000000000 ); // 0が18個
// // CIN_ASSERT( N , 0 , bound_N );
// CEXPR( int , bound_M , 100000 ); // 0が5個
// // CEXPR( ll , bound_M , 1000000000 ); // 0が9個
// // CEXPR( ll , bound_M , 1000000000000000000 ); // 0が18個
// CIN_ASSERT( M , 0 , bound_M );
CEXPR( int , bound_pq , 1000000000 ); // 0が9個
PrimeEnumeration<int,100000,100000> pe{};
int p[2];
int q[2];
int r[2];
list<int> d[2];
int& p0 = p[0];
int& q0 = q[0];
int& r0 = r[0];
list<int>& d0 = d[0];
int& p1 = p[1];
int& q1 = q[1];
int& r1 = r[1];
list<int>& d1 = d[1];
REPEAT( Q ){
FOR( i , 0 , 2 ){
int& pi = p[i];
int& qi = q[i];
int& ri = r[i];
cin >> pi >> qi;
assert( 1 <= pi && pi < qi && qi <= bound_pq );
ri = qi - pi;
}
CERR( q0 << "-" << p0 << "=" << r0 << "," << q1 << "-" << p1 << "=" << r1 );
while( true ){
if( r0 > r1 || ( r0 == r1 && p0 < p1 ) ){
swap( p0 , p1 );
swap( q0 , q1 );
swap( r0 , r1 );
swap( d0 , d1 );
}
d1 = EnumerateDivisor( pe , r1 );
d1.pop_front();
int p1_next = bound_pq;
while( ! d1.empty() ){
int& d1_curr = d1.front();
int temp = ( p1 + d1_curr - 1 ) / d1_curr * d1_curr;
( p1_next > temp ) ? p1_next = temp : p1_next;
d1.pop_front();
}
if( r0 == r1 ){
if( p1_next > p0 ){
break;
}
}
q1 += p1_next - p1;
p1 = p1_next;
r1 = q1 - p1;
int gcd = GCD( p1 , q1 );
p1 /= gcd;
q1 /= gcd;
r1 /= gcd;
CERR( q0 << "-" << p0 << "=" << r0 << "," << q1 << "-" << p1 << "=" << r1 );
}
COUT( p0 << " " << q0 );
}
QUIT;
}