結果
| 問題 | No.2360 Path to Integer |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2023-07-30 20:45:06 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 82 ms / 2,500 ms |
| コード長 | 57,089 bytes |
| コンパイル時間 | 4,119 ms |
| コンパイル使用メモリ | 248,592 KB |
| 実行使用メモリ | 30,884 KB |
| 最終ジャッジ日時 | 2024-04-27 04:52:57 |
| 合計ジャッジ時間 | 5,637 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 7 ms
19,728 KB |
| testcase_01 | AC | 5 ms
20,236 KB |
| testcase_02 | AC | 7 ms
21,136 KB |
| testcase_03 | AC | 6 ms
20,500 KB |
| testcase_04 | AC | 6 ms
19,860 KB |
| testcase_05 | AC | 6 ms
21,044 KB |
| testcase_06 | AC | 7 ms
20,108 KB |
| testcase_07 | AC | 7 ms
20,196 KB |
| testcase_08 | AC | 12 ms
20,512 KB |
| testcase_09 | AC | 82 ms
27,756 KB |
| testcase_10 | AC | 69 ms
30,884 KB |
| testcase_11 | AC | 71 ms
30,868 KB |
| testcase_12 | AC | 61 ms
27,740 KB |
| testcase_13 | AC | 82 ms
27,772 KB |
| testcase_14 | AC | 71 ms
27,944 KB |
| testcase_15 | AC | 76 ms
27,800 KB |
| testcase_16 | AC | 68 ms
27,776 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( MESSAGE ) cerr << MESSAGE << 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; };
#define START_WATCH( PROCESS_NAME ) StartWatch( PROCESS_NAME )
#define STOP_WATCH( HOW_MANY_TIMES ) StopWatch( HOW_MANY_TIMES )
#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( MESSAGE )
#define COUT( ANSWER ) cout << ANSWER << "\n"
#define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
#define LIBRARY_SEARCH
#define START_WATCH( PROCESS_NAME )
#define STOP_WATCH( HOW_MANY_TIMES )
#endif
// #define RANDOM_TEST
#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 ) TYPE_OF( MAX ) A; SET_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 AUTO_ITR( ARRAY ) auto itr_ ## ARRAY = ARRAY .begin() , end_ ## ARRAY = ARRAY .end()
#define FOR_ITR( ARRAY ) for( AUTO_ITR( ARRAY ) , itr = itr_ ## ARRAY ; itr_ ## ARRAY != end_ ## ARRAY ; itr_ ## ARRAY ++ , itr++ )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT_ ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES )
#define QUIT return 0
#define SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS_ )
#ifdef DEBUG
inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); }
void StartWatch( const string& process_name = "nothing" );
void StopWatch( const int& how_many_times = 1 );
#endif
#if defined( DEBUG ) && defined( RANDOM_TEST )
inline CEXPR( int , bound_random_test_num , 1000 );
#define START_MAIN FOR( random_test_num , 0 , bound_random_test_num ){ CERR( "(" << random_test_num << ")" );
ll GetRand( const ll& Rand_min , const ll& Rand_max );
#define SET_ASSERT( A , MIN , MAX ) CERR( #A << " = " << ( A = GetRand( MIN , MAX ) ) )
#define RETURN( ANSWER ) if( ( ANSWER ) == guchoku ){ CERR( ( ANSWER ) << " == " << guchoku ); continue; } else { CERR( ( ANSWER ) << " != " << guchoku ); QUIT; }
#define FINISH_MAIN CERR( "" ); }
#else
#define START_MAIN
#define SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX )
#define RETURN( ANSWER ) COUT( ( ANSWER ) ); QUIT
#define FINISH_MAIN
#endif
template <typename T> inline T Absolute( const T& a ){ return a > 0 ? a : -a; }
template <typename T> inline T Residue( const T& a , const T& p ){ return a >= 0 ? a % p : p - 1 - ( ( - ( a + 1 ) ) % 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 , DESIRED_INEQUALITY , TARGET , INEQUALITY_FOR_CHECK , 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_FOR_CHECK 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 << ( EXPRESSION > TARGET ? ">" : EXPRESSION < TARGET ? "<" : "=" ) << TARGET ); \
CERR( ( EXPRESSION DESIRED_INEQUALITY TARGET ? "二分探索成功" : "二分探索失敗" ) ); \
assert( EXPRESSION DESIRED_INEQUALITY TARGET ); \
} else { \
CERR( "二分探索失敗： " << MINIMUM << ">" << MAXIMUM ); \
assert( 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&
#define ASK_NUMBER( ... ) \
CERR( "問題の区分は以下の中で何番に該当しますか？" ); \
problems = { __VA_ARGS__ }; \
problems_size = problems.size(); \
FOR( i , 0 , problems_size ){ \
CERR( i << ": " << problems[i] ); \
} \
cin >> num; \
CERR( "" ); \
num_temp = 0; \
if( num < 0 || num >= problems_size ){ \
CERR( "返答は" << problems_size - 1 << "以下の非負整数にしてください。" ); \
CERR( "終了します。" ); \
CERR( "" ); \
return -1; \
} \
#define ASK_YES_NO( QUESTION ) \
CERR( QUESTION << "[y/n]" ); \
cin >> reply; \
if( reply != "y" && reply != "n" ){ \
CERR( "y/nのいずれかで答えてください。" ); \
CERR( "終了します。" ); \
CERR( "" ); \
return -1; \
} \
CERR( "" ); \
int LibrarySearch( int num = -1 )
{
vector<string> problems{};
int problems_size = 13;
int num_temp = 0;
string reply{};
if( num == -1 ){
ASK_YES_NO( "ライブラリーを探索しますか？" );
if( reply == "y" ){
CERR( "ライブラリーを探索します。" );
} else {
CERR( "ライブラリーを探索せずに続行します。" );
CERR( "" );
return 0;
}
ASK_NUMBER(
"数や関数に関する問題。" ,
"配列に関する問題。" ,
"文字列に関する問題。" ,
"順列に関する問題。" ,
"矩形領域に関する問題。" ,
"グラフに関する問題。" ,
"確率／期待値に関する問題。" ,
"ゲームに関する問題。" ,
"論理に関する問題。" ,
"半順序集合に関する問題。" ,
"関数適用に関する問題。" ,
"構築問題。"
);
} else {
CERR( "" );
}
CEXPR( int , num_graph , 5 );
CEXPR( int , num_game , 7 );
if( num == num_temp++ ){
ASK_YES_NO( "入力は１つの数か、１つの数と法を表す数ですか？" );
if( reply == "y" ){
CERR( "まずは小さい入力の場合を愚直に計算し、OEISで検索しましょう。" );
CERR( "https://oeis.org/?language=japanese" );
CERR( "" );
CERR( "次に出力の定義と等価な式を考察しましょう。" );
CERR( "- 単調ならば、冪乗や階乗" );
CERR( "- 定義にp進法が使われていれば、各種探索アルゴリズム" );
CERR( "- 入力が素数に近い場合に規則性があれば、p進付値、p進法、" );
CERR( " オイラー関数、約数の個数など" );
CERR( "を検討しましょう。" );
} else {
ASK_NUMBER(
"求解問題。" ,
"最大化問題。" ,
"数え上げ問題。" ,
"ソート問題。"
);
if( num == num_temp++ ){
CERR( "まず" );
CERR( "- 単調関数は二分探索" );
CERR( "- 可微分関数はニュートン法" );
CERR( "- 一次関数は掃き出し法" );
CERR( "を検討しましょう。" );
CERR( "" );
CERR( "それらが間に合わない時は" );
CERR( "- 探索範囲を絞れそうな場合は全探策" );
CERR( "- 多変数の合成関数で表せる場合は半分全列挙" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "- 凸関数は三分探索" );
CERR( "- 可微分関数は微分のニュートン法" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "- 変数の対称性があれば大小関係を制限した全探策" );
CERR( "- 何らかの約数となるなど動く範囲が狭い変数があればそれらを決め打った全探策" );
CERR( "- 多変数の合成関数で表せる場合は半分全列挙" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "集合Sを何らかの順序でソートした配列aに関する問題で、" );
CERR( "- 与えられた要素sが下から何番目かを答える場合は、非負整数iごとに" );
CERR( " 不等式a[i]<=sを判定する方法を考察し、iに関する二分探索" );
CERR( "- 与えられた非負整数iに対するa[i]を答える場合は、Sの要素sごとに" );
CERR( " 不等式a[i]<=sを判定する方法を考察し、sに関する二分探索" );
CERR( "を検討しましょう。" );
}
}
CERR( "" );
ASK_YES_NO( "マルチテストケースですか？" );
if( reply == "y" ){
CERR( "テストケース全体でのNの総和に直接上限が与えられている問題では、" );
CERR( "ライブラリーの使用時は、配列の初期化が各テストケースに必要となる場合に" );
CERR( "TLEとなる可能性が高いです。適宜動的配列に置き換えましょう。" );
CERR( "" );
CERR( "配列を手元の環境でデバッグしやすくするためにstaticをつけている場合は" );
CERR( "テストケースを跨いで値が残ってしまわないように注意しましょう。" );
CERR( "" );
CERR( "前計算の候補としては" );
CERR( "- 素数列挙" );
CERR( "- １つまたは複数の整数の約数列挙" );
CERR( "- オイラー関数の値の列挙" );
CERR( "- サブゴールとなる関係式を満たす解の列挙" );
CERR( "を検討しましょう。" );
} else {
CERR( "入力が大きい場合と小さい場合で解法を変える考察を忘れないようにしましょう。" );
}
CERR( "" );
} else if( num == num_temp++ ){
ASK_YES_NO( "入力に配列が与えられますか？" );
if( reply == "y" ){
ASK_NUMBER(
"区間等の領域処理問題。" ,
"成分を受け取る関数の総和問題" ,
"部分列を受け取る関数の総和問題" ,
"その他の関数に関する問題。" ,
"隣接成分間関係式に関する問題。"
);
if( num == num_temp++ ){
ASK_NUMBER(
"可換群構造+を使う問題。" ,
"可換羃等モノイド構造∨を使う問題。" ,
"モノイド構造*を使う問題。" ,
"非結合的マグマ構造*を使う問題。" ,
"集合へのマグマ作用(*,\\cdot)を使う問題。" ,
"モノイドへのマグマ作用(+,\\cdot)を使う問題。" ,
"定数とのmaxを取った値の区間和取得を使う問題。"
);
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++ ){
ASK_YES_NO( "総和を取る前に配列に操作をする問題ですか？" );
if( reply == "y" ){
CERR( "関数が一次式の場合、実質内積と定数の和となります。" );
CERR( "内積は片方の添え字を反転させることで畳み込みに帰着させることができます。" );
CERR( "配列への操作がシフトである場合は繰り返し内積を求めることになるので、" );
CERR( "適当な法での高速フーリエ変換" );
CERR( "\\Mathematics\\Arithmetic\\Mod" );
CERR( "\\Mathematics\\Polynoial" );
} else {
CERR( "関数を予め各成分に適用してしまえば、ただの総和に関する問題となります。" );
CERR( "" );
ASK_NUMBER(
"部分和の最大化問題。" ,
"部分和を固定した部分列の数え上げ問題。" ,
);
if( num == num_temp++ ){
CERR( "項数N、重みの総和の上限W（多変数も可）、価値（和を取る値）の上限Vとします。" );
CERR( "- B=∞ならば、通常のナップサック問題と同様の動的計画法" );
CERR( "- B<∞でO(2^N)が通りそうならば愚直に全探策" );
CERR( "- B<∞でO(N 2^{N/2})が通りそうならば半分全列挙" );
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" );
CERR( "- 選択に順序と制約がある場合、O(N 2^N)が通りそうならばbit全探策" );
} 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\\Arithmetic\\Mod" );
CERR( " \\Mathematics\\Polynomial" );
}
}
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "配列を受け取る関数fが与えられているとします。" );
CERR( "以下、連続部分列を扱う問題について考えます。" );
CERR( "連続とは限らない部分列の場合、分割に区間でなく部分集合を使います。" );
CERR( "" );
CERR( "配列Aの分割Pに対し、Pの各成分pを渡るf(p)の総和をF(P)と置きます。" );
ASK_YES_NO( "fがbit演算である問題ですか？" );
if( reply == "y" ){
CERR( "「配列の第i成分までで切った時にj桁目に1の立つ個数dp[i][j]」" );
CERR( "を管理するi,jに関する動的計画法を検討しましょう。" );
CERR( "更にその計算量を評価し、適宜bitsetやデータ構造で高速化しましょう。" );
} else {
CERR( "Pの末尾pを削除した分割P'が元の配列からpを削除した配列の分割であり" );
CERR( "F(P)=F(P')+f(p)と表せることに注意して、" );
CERR( "- F(P)の最大化問題は" );
CERR( " 「第i成分までで切った時のF(P)たちの最大値dp[i]」" );
CERR( " を管理するiに関する動的計画法（O(N^2×fの計算量)）" );
CERR( "- F(P)が固定された時のPの数え上げ問題は" );
CERR( " 「第i成分までで切った時のF(P)=vを満たすPの個数dp[i][v]」" );
CERR( " を管理するi,vに関する動的計画法（O(N^2 v_max×fの計算量)）" );
CERR( "を検討しましょう。" );
CERR( "" );
CERR( "更にfが部分列の長さに関する再帰的な構造を持つ場合、全ての連続部分列に" );
CERR( "対しfの値を前計算することを検討しましょう。" );
}
} else if( num == num_temp++ ){
CERR( "配列を受け取る関数Fが与えられているとします。与えられた配列Aに" );
CERR( "何らかの処理をして得られる配列Bに対するF(B)の最大化問題は、" );
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(N))が通りそうで" );
CERR( " - fがxからO(N)で計算できxに関して単調ならば、xの二分探索" );
CERR( " - 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++ ){
ASK_NUMBER(
"関係式を満たす部分列の最長化問題。" ,
"関係式を満たす部分列の数え上げ問題。"
);
if( num == num_temp++ ){
CERR( "全順序か疎な半順序かで効率的な実装が違います。" );
CERR( "- 全順序ならば、条件を満たす部分列の長さの最大値をインデックスに持つ" );
CERR( " 配列を用いて、それらの部分列の末尾である項を記録すること" );
CERR( " \\Mathematics\\Combinatorial\\Counting\\IncreasingSubsequence" );
CERR( "- 疎な半順序ならば、条件を満たす部分列の末尾をインデックスに持つ" );
CERR( " 連想配列を用いて、それら部分列の長さの最大値を記録すること" );
CERR( " \\Mathematics\\Combinatorial\\Counting\\IncreasingSubsequence\\Subwalk" );
CERR( "を検討しましょう。" );
} else {
ASK_NUMBER(
"連続部分列の数え上げ問題。" ,
"連続とは限らない部分列の数え上げ問題。" ,
"部分順列（部分列の並び換え）の数え上げ問題。" ,
);
CERR( "長さNの配列Aと、L+n<=N+1を満たす整数n,Lと" );
CERR( "- 整数iに関する条件Q(i)" );
CERR( "- 各0<=l<Lに対するn-tuple(b_0,...,b_{n-1})に関する条件R_l(b_0,...,b_{n-1})" );
CERR( "が与えられているとし、配列Bの条件P(B)を" );
CERR( "「Bの長さ|B|がQ(|B|)かつ|B|<L+nを満たし、かつ任意の0<=l<=|B|-nに対し" );
CERR( " R_l(B_l,...,B_{l+n-1})が成り立つ。」" );
CERR( "の論理積として定めます。" );
CERR( "" );
CERR( "例えば山型の部分列の数え上げ問題ではN>=3かつ(n,L)=(2,2)で" );
CERR( "- Q(i)=「i=3」" );
CERR( "- R_0(b_0,b_1)=「b_0<b_1」" );
CERR( "- R_1(b_0,b_1)=「b_0>b_1」" );
CERR( "と表されます。" );
CERR( "" );
if( num == num_temp++ ){
CERR( "P(B)を満たすAの連続部分列Bの数え上げは、" );
CERR( "- R_lたちがlに依存しないならば尺取り法O(N)" );
CERR( "- R_lたちがlに依存する場合、" );
CERR( " - O(N^2)が通りそうなら左端を固定した愚直探索" );
CERR( " - O(N^2)が通らなさそうならR_lたちの読み替え" );
} else if( num == num_temp++ ){
CERR( "P(B)を満たすAの連続とは限らない部分列Bの数え上げは、" );
CERR( "- n-1<=i<=max{j<=N|Q(j)}を満たす各i" );
CERR( "- (0,1,...,N-1)の長さn-1の各部分列s" );
CERR( "に対する" );
CERR( "「長さiで、任意の0<=l<=i-nに対しR_l(B)を満たし、" );
CERR( " 末尾n-1項がsに対応するAの部分列Bの個数dp[i][s]」" );
CERR( "を管理するi,sに関する動的計画法" );
CERR( "\\Mathematics\\Combinatorial\\Counting\\IncreasingSubsequence" );
CERR( "\\Mathematics\\Combinatorial\\Counting\\IncreasingSubsequence\\Subwalk" );
} else if( num == num_temp++ ){
CERR( "P(B)を満たすAの部分順列Bの数え上げは、" );
CERR( "- n-1<=|S|<=max{j<=N|Q(j)}を満たす(0,1,...,N-1)の部分集合S" );
CERR( "- Sの長さn-1の各部分順列s" );
CERR( "に対する" );
CERR( "「任意の0<=l<=|S|-nに対しR_l(B)を満たし、末尾n-1項がsに対応し、」" );
CERR( " 全体がSに対応するAの部分順列Bの個数dp[S][s]」" );
CERR( "を管理するS,sに関する動的計画法を検討しましょう。" );
CERR( "" );
CERR( "sの網羅は[0,N)^{n-1}の全探策でもS内の順列探索と定数倍しか変わらないので" );
CERR( "実装の速さを優先しましょう。" );
CERR( "" );
CERR( "Nが小さい場合は概算値" );
CERR( "7! ≒ 5×10^3" );
CERR( "8! ≒ 4×10^4" );
CERR( "9! ≒ 4×10^5" );
CERR( "10! ≒ 4×10^6" );
CERR( "11! ≒ 4×10^7" );
CERR( "12! ≒ 5×10^8" );
CERR( "を参考に順列の全列挙" );
CERR( "\\Mathematics\\Combinatorial\\Permutation" );
}
CERR( "を検討しましょう。" );
CERR( "" );
CERR( "特にR_l(B)たちがgcdやmaxなどの羃等演算に関する等式で与えられる場合は、" );
CERR( "不等式の方が扱いやすいのでゼータ変換／メビウス変換を検討しましょう。" );
}
}
} else {
ASK_NUMBER(
"配列を受け取る関数に関する問題。" ,
"隣接成分間関係式に関する問題。"
);
if( num == num_temp++ ){
ASK_NUMBER(
"最大化問題。" ,
"数え上げ問題。"
);
if( num == num_temp++ ){
CERR( "- 取り得る値が少なく関数が長さに関して再帰的構造を持つ場合は、" );
CERR( " 「長さiの時に可能な値全体または一部の集合dp[i]」" );
CERR( " を管理するiに関する動的計画法" );
CERR( "- 「v以上の値を取り得るか否か」が判定可能である時は" );
CERR( " vに関する二分探索" );
} else {
CERR( "- マルチテストケースで配列の種類が少ない場合は、" );
CERR( " 全ての配列に対する関数の値の前計算" );
CERR( "- 取り得る値が少なく関数が長さに関して再帰的構造を持つ場合は、" );
CERR( " 「長さiの時に値vである配列の総数dp[i][v]」" );
CERR( " を管理するi,vに関する動的計画法" );
}
} else {
CERR( "- いくつかの条件の重ね合わせの時は包除原理" );
CERR( "- 全順序の場合は数の分割方法などへの翻訳" );
CERR( "- 疎な半順序の場合はグラフの前計算" );
}
CERR( "を検討しましょう。" );
}
} else if( num == num_temp++ ){
ASK_NUMBER(
"部分列マッチング問題。" ,
"回文探索問題。"
);
if( num == num_temp++ ){
CERR( "基本的には丁寧にループを回して解きましょう。" );
CERR( "- 比較対象が少ない場合、前または後ろから順に探索（貪欲法／動的計画法）" );
CERR( "- ワイルドカードを含む場合、" );
CERR( " - 前または後ろから順に場合分けをしてO(N)で処理できるか" );
CERR( " - 可能な代入方法を絞り込んでO(N)種類に落せるか" );
CERR( "- 比較回数が多い場合、ローリングハッシュ" );
CERR( " \\Utility\\String\\RollingHash" );
CERR( "- マッチングする文字列の最長化をする場合、Zアルゴリズム" );
CERR( " https://qiita.com/Pro_ktmr/items/16904c9570aa0953bf05" );
CERR( "- マッチングする文字数の最大化をする場合、文字の種類分の{0,1}値配列に" );
CERR( " 分けて内積の最大化（添え字を反転させて適当な法での畳み込み）" );
CERR( " \\Mathematics\\Arithmetic\\Mod" );
CERR( " \\Mathematics\\Polynomial" );
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++ ){
ASK_NUMBER(
"探索問題。" ,
"絶対値の最小／最大化問題。" ,
"その他の最小／最大化問題。"
);
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++ ){
ASK_NUMBER(
"２点最短径路（迷路）問題。" ,
"多点最短経路（スタンプラリー）問題。" ,
"木の問題。" ,
"連結性問題。"
);
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( "確率計算は" );
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++ ){
ASK_NUMBER(
"関数の計算問題。" ,
"降下／上昇列に関する問題。"
);
if( num == num_temp++ ){
CERR( "ゼータ変換を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "順序関係の定める有向グラフの問題に帰着させましょう。" );
return LibrarySearch( num = num_graph );
}
} else if( num == num_temp++ ){
ASK_NUMBER(
"反復合成の計算問題。" ,
"反復合成による到達可能性問題。"
);
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++ ){
ASK_NUMBER(
"数や配列や文字列の構築。" ,
"経路の構築。" ,
"戦略の構築。" ,
"ソースコードの構築。"
);
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 );
} else if( num == num_temp++ ){
CERR( "正解を出力をするソースコードを提出しましょう。" );
return LibrarySearch( num = num_game );
}
}
CERR( "" );
CERR( "ライブラリー探索は以上です。終了します。" );
CERR( "" );
return -1;
}
// Resetはm_foundとm_prevを初期化
// Shiftはm_foundとm_prevを非初期化
#define DECLARATION_OF_FIRST_SEARCH( BREADTH ) \
template <int V_max> \
class BREADTH ## FirstSearch_Body \
{ \
\
protected: \
int m_V; \
int m_init; \
list<int> m_next; \
bool m_found[V_max]; \
int m_prev[V_max]; \
\
public: \
inline BREADTH ## FirstSearch_Body( const int& V ); \
inline BREADTH ## FirstSearch_Body( const int& V , const int& init ); \
\
inline void Reset( const int& init ); \
inline void Shift( const int& init ); \
\
inline const int& size() const; \
inline const int& init() const; \
inline bool& found( const int& i ); \
inline const int& prev( const int& i ) const; \
\
int Next(); \
\
private: \
virtual list<int> e( const int& t ) = 0; \
\
}; \
\
template <int V_max,list<int> E(const int&)> \
class BREADTH ## FirstSearch : \
public BREADTH ## FirstSearch_Body<V_max> \
{ \
\
public: \
\
template<typename... Args> inline BREADTH ## FirstSearch( const Args&... args ); \
\
private: \
inline list<int> e( const int& t ); \
\
}; \
\
template <int V_max,list<int> E(const int&)> void BREADTH ## FirstConnectedComponent( const int& V , int ( &vertex )[V_max] , int& count ); \
#define DEFINITION_OF_FIRST_SEARCH( BREADTH , PUSH ) \
template <int V_max> inline BREADTH ## FirstSearch_Body<V_max>::BREADTH ## FirstSearch_Body( const int& V ) : m_V( V ) , m_init() , m_next() , m_found() , m_prev() { assert( m_V <= V_max ); for( int i = 0 ; i < m_V ; i++ ){ m_prev[i] = -1; } } \
template <int V_max> inline BREADTH ## FirstSearch_Body<V_max>::BREADTH ## FirstSearch_Body( const int& V , const int& init ) : BREADTH ## FirstSearch_Body( V ) { m_init = init; m_next.push_back( m_init ); m_found[m_init] = true; } \
template <int V_max,list<int> E(const int&)> template <typename... Args> inline BREADTH ## FirstSearch<V_max,E>::BREADTH ## FirstSearch( const Args&... args ) : BREADTH ## FirstSearch_Body<V_max>( args... ) {} \
\
template <int V_max> inline void BREADTH ## FirstSearch_Body<V_max>::Reset( const int& init ) { m_init = init; assert( m_init < m_V ); m_next.clear(); m_next.push_back( m_init ); for( int i = 0 ; i < m_V ; i++ ){ m_found[i] = i == m_init; m_prev[i] = -1; } } \
template <int V_max> inline void BREADTH ## FirstSearch_Body<V_max>::Shift( const int& init ) { m_init = init; assert( m_init < m_V ); m_next.clear(); if( ! m_found[m_init] ){ m_next.push_back( m_init ); m_found[m_init] = true; } } \
\
template <int V_max> inline const int& BREADTH ## FirstSearch_Body<V_max>::size() const { return m_V; } \
template <int V_max> inline const int& BREADTH ## FirstSearch_Body<V_max>::init() const { return m_init; } \
template <int V_max> inline bool& BREADTH ## FirstSearch_Body<V_max>::found( const int& i ) { assert( i < m_V ); return m_found[i]; } \
template <int V_max> inline const int& BREADTH ## FirstSearch_Body<V_max>::prev( const int& i ) const { assert( i < m_V ); return m_prev[i]; } \
\
template <int V_max> \
int BREADTH ## FirstSearch_Body<V_max>::Next() \
{ \
\
if( m_next.empty() ){ \
\
return -1; \
\
} \
\
const int i_curr = m_next.front(); \
m_next.pop_front(); \
list<int> edge = e( i_curr ); \
\
while( ! edge.empty() ){ \
\
const int& i = edge.front(); \
bool& found_i = found( i ); \
\
if( ! found_i ){ \
\
m_next.PUSH( i ); \
m_prev[i] = i_curr; \
found_i = true; \
\
} \
\
edge.pop_front(); \
\
} \
\
return i_curr; \
\
} \
\
template <int V_max,list<int> E(const int&)> inline list <int> BREADTH ## FirstSearch<V_max,E>::e( const int& t ) { return E( t ); } \
\
template <int V_max,list<int> E(const int&)> void BREADTH ## FirstConnectedComponentSearch( const int& V , int ( &vertex )[V_max] , int& count ) \
{ \
\
BREADTH ## FirstSearch<V_max,E> bfs{ V }; \
count = 0; \
\
for( int i = 0 ; i < V ; i++ ){ \
\
vertex[i] = -1; \
\
} \
\
for( int i = 0 ; i < V ; i++ ){ \
\
if( vertex[i] == -1 ){ \
\
bfs.Shift( i ); \
int j = bfs.Next(); \
\
while( j != -1 ? vertex[j] == 0 : false ){ \
\
vertex[j] = count; \
j = bfs.Next(); \
\
} \
\
count++; \
\
} \
\
} \
\
return; \
\
} \
DECLARATION_OF_FIRST_SEARCH( Depth );
DEFINITION_OF_FIRST_SEARCH( Depth , push_front );
// 2^16 = 65536
// 2^17 = 131072
// 2^18 = 262144
template <int V_max,list<int> E(const int&),int digit = 0>
class DepthFirstSearchOnTree :
public DepthFirstSearch<V_max,E>
{
private:
// メモリが厳しい場合、以下で不要なものを消す。
int m_reversed[V_max];
list<int> m_children[V_max];
bool m_set_children;
int m_depth[V_max];
int m_height[V_max];
bool m_set_height;
int m_weight[V_max];
bool m_set_weight;
int m_doubling[digit][V_max];
bool m_set_doubling;
public:
inline DepthFirstSearchOnTree( const int& V , const int& root );
inline void Reset( const int& init ) = delete;
inline void Shift( const int& init ) = delete;
inline const int& Root() const;
inline const int& Parent( const int& i ) const;
inline const list<int>& Children( const int& i );
inline const int& Depth( const int& i ) const;
inline const int& Height( const int& i );
inline const int& Weight( const int& i );
// 探索順にノードを番号づける。
inline const int& Node( const int& i , const bool& reversed = false ) const;
// 各ノードの高さ < 2^digitの時のみサポート。
int Ancestor( int i , int n );
int LCA( int i , int j );
int LCA( int i , int j , int& i_prev , int& j_prev );
private:
void SetChildren();
void SetHeight();
void SetWeight();
// 各ノードの高さ < 2^digitの時のみサポート。
// LCA()を呼ぶ前にAncestor()経由で完全にダブリングを設定するため、
// 遅延評価する../../../../Mathematics/Function/Iteration/Doubling/のダブリングで代用しない。
void SetDoubling();
};
template <int V_max,list<int> E(const int&),int digit> inline DepthFirstSearchOnTree<V_max,E,digit>::DepthFirstSearchOnTree( const int& V , const int& root ) :
DepthFirstSearch<V_max,E>( V , root ) , m_reversed() , m_children() , m_set_children() , m_depth() , m_height() , m_set_height() , m_weight() , m_set_weight() , m_doubling() , m_set_doubling()
{
int n = DepthFirstSearch<V_max,E>::size();
while( --n >= 0 ){
const int& i = m_reversed[n] = DepthFirstSearch<V_max,E>::Next();
const int& j = Parent( i );
if( j != -1 ){
m_depth[i] = m_depth[j] + 1;
}
}
}
template <int V_max,list<int> E(const int&),int digit> inline const int& DepthFirstSearchOnTree<V_max,E,digit>::Root() const { return DepthFirstSearch<V_max,E>::init(); }
template <int V_max,list<int> E(const int&),int digit> inline const int& DepthFirstSearchOnTree<V_max,E,digit>::Parent( const int& i ) const { return DepthFirstSearch<V_max,E>::prev( i ); }
template <int V_max,list<int> E(const int&),int digit> inline const list<int>& DepthFirstSearchOnTree<V_max,E,digit>::Children( const int& i ) { if( ! m_set_children ){ SetChildren(); } return m_children[i]; }
template <int V_max,list<int> E(const int&),int digit> inline const int& DepthFirstSearchOnTree<V_max,E,digit>::Depth( const int& i ) const { return m_depth[i]; }
template <int V_max,list<int> E(const int&),int digit> inline const int& DepthFirstSearchOnTree<V_max,E,digit>::Height( const int& i ) { if( ! m_set_height ){ SetHeight(); } return m_height[i]; }
template <int V_max,list<int> E(const int&),int digit> inline const int& DepthFirstSearchOnTree<V_max,E,digit>::Weight( const int& i ) { if( ! m_set_weight ){ SetWeight(); } return m_weight[i]; }
template <int V_max,list<int> E(const int&),int digit> inline const int& DepthFirstSearchOnTree<V_max,E,digit>::Node( const int& i , const bool& reversed ) const { return m_reversed[reversed ? i : DepthFirstSearch<V_max,E>::m_V - 1 - i]; }
template <int V_max,list<int> E(const int&),int digit>
int DepthFirstSearchOnTree<V_max,E,digit>::Ancestor( int i , int n )
{
if( ! m_set_doubling ){
SetDoubling();
}
assert( ( n >> digit ) == 0 );
int d = 0;
while( n != 0 ){
if( ( n & 1 ) == 1 ){
assert( ( i = m_doubling[d][i] ) != -1 );
}
d++;
n >>= 1;
}
return i;
}
template <int V_max,list<int> E(const int&),int digit>
int DepthFirstSearchOnTree<V_max,E,digit>::LCA( int i , int j )
{
int diff = Depth( i ) - Depth( j );
if( diff < 0 ){
swap( i , j );
diff *= -1;
}
i = Ancestor( i , diff );
if( i == j ){
return i;
}
int d = digit;
while( --d >= 0 ){
const int ( &doubling_d )[V_max] = m_doubling[d];
const int& doubling_d_i = doubling_d[i];
const int& doubling_d_j = doubling_d[j];
if( doubling_d_i != doubling_d_j ){
i = doubling_d_i;
j = doubling_d_j;
assert( i != -1 );
assert( j != -1 );
}
}
return Parent( i );
}
template <int V_max,list<int> E(const int&),int digit>
int DepthFirstSearchOnTree<V_max,E,digit>::LCA( int i , int j , int& i_prev , int& j_prev )
{
if( i == j ){
i_prev = j_prev = -1;
return i;
}
int diff = Depth( i ) - Depth( j );
if( diff < 0 ){
return LCA( j , i , j_prev , i_prev );
}
if( diff > 0 ){
i_prev = Ancestor( i , diff - 1 );
i = Parent( i_prev );
assert( i != -1 );
if( i == j ){
j_prev = -1;
return i;
}
} else if( ! m_set_doubling ){
SetDoubling();
}
int d = digit;
while( --d >= 0 ){
const int ( &doubling_d )[V_max] = m_doubling[d];
const int& doubling_d_i = doubling_d[i];
const int& doubling_d_j = doubling_d[j];
if( doubling_d_i != doubling_d_j ){
i = doubling_d_i;
j = doubling_d_j;
assert( i != -1 );
assert( j != -1 );
}
}
i_prev = i;
j_prev = j;
return Parent( i_prev );
}
template <int V_max,list<int> E(const int&),int digit>
void DepthFirstSearchOnTree<V_max,E,digit>::SetChildren()
{
assert( !m_set_children );
m_set_children = true;
const int& V = DepthFirstSearch<V_max,E>::size();
for( int i = 0 ; i < V ; i++ ){
const int& parent_i = Parent( i );
if( parent_i != -1 ){
m_children[parent_i].push_back( i );
}
}
return;
}
template <int V_max,list<int> E(const int&),int digit>
void DepthFirstSearchOnTree<V_max,E,digit>::SetHeight()
{
assert( !m_set_height );
m_set_height = true;
const int& V = DepthFirstSearch<V_max,E>::size();
for( int i = 0 ; i < V ; i++ ){
const int& reversed_i = m_reversed[i];
const int& parent_i = Parent( reversed_i );
if( parent_i != -1 ){
int& height_parent_i = m_height[parent_i];
const int& height_i = m_height[reversed_i];
height_parent_i > height_i ? height_parent_i : height_parent_i = height_i + 1;
}
}
return;
}
template <int V_max,list<int> E(const int&),int digit>
void DepthFirstSearchOnTree<V_max,E,digit>::SetWeight()
{
assert( !m_set_weight );
m_set_weight = true;
const int& V = DepthFirstSearch<V_max,E>::size();
for( int i = 0 ; i < V ; i++ ){
const int& reversed_i = m_reversed[i];
const int& parent_i = Parent( reversed_i );
if( parent_i != -1 ){
m_weight[parent_i] += m_weight[reversed_i] + 1;
}
}
return;
}
template <int V_max,list<int> E(const int&),int digit>
void DepthFirstSearchOnTree<V_max,E,digit>::SetDoubling()
{
assert( !m_set_doubling );
m_set_doubling = true;
const int& V = DepthFirstSearch<V_max,E>::size();
{
int ( &doubling_0 )[V_max] = m_doubling[0];
const int& r = Root();
for( int i = 0 ; i < V ; i++ ){
doubling_0[i] = Parent( i );
}
}
for( int d = 1 ; d < digit ; d++ ){
int ( &doubling_d )[V_max] = m_doubling[d];
int ( &doubling_d_minus )[V_max] = m_doubling[d-1];
for( int i = 0 ; i < V ; i++ ){
const int& doubling_d_minus_i = doubling_d_minus[i];
doubling_d[i] = doubling_d_minus_i == -1 ? -1 : doubling_d_minus[doubling_d_minus_i];
}
}
return;
}
inline DEXPR( int , bound_N , 100000 , 100 ); // 0が5個
list<int> e[bound_N] = {};
inline list<int> E( const int& i ) { return e[i]; }
int main()
{
UNTIE;
LIBRARY_SEARCH;
START_MAIN;
// DEXPR( int , bound_T , 100000 , 100 );
// CIN_ASSERT( T , 1 , bound_T );
// REPEAT( T ){
// }
// CEXPR( int , bound_N , 10 );
// CEXPR( int , bound_N , 1000000000 ); // 0が9個
// CEXPR( ll , bound_N , 1000000000000000000 ); // 0が18個
CIN_ASSERT( N , 0 , bound_N );
CEXPR( ll , P , 998244353 );
// CEXPR( ll , P , 1000000007 );
ll power_10[11] = { 1 };
FOREQ( i , 1 , 10 ){
power_10[i] = power_10[i-1] * 10;
}
CEXPR( ll , bound_A , 10000000000 );
ll A[bound_N];
ll length[bound_N];
FOR( i , 0 , N ){
CIN_ASSERT( Ai , 1 , bound_A );
FOREQ( d , 1 , 10 ){
if( Ai < power_10[d] ){
length[i] = d;
break;
}
}
A[i] = Ai;
}
FOREQ( i , 1 , 10 ){
power_10[i] %= P;
}
FOR( i , 1 , N ){
CIN_ASSERT( ui , 1 , N );
CIN_ASSERT( vi , 1 , N );
assert( --ui != --vi );
e[ui].push_back( vi );
e[vi].push_back( ui );
}
// // CEXPR( int , bound_M , 10 );
// DEXPR( int , bound_M , 100000 , 100 ); // 0が5個
// // CEXPR( int , bound_M , 1000000000 ); // 0が9個
// // CEXPR( ll , bound_M , 1000000000000000000 ); // 0が18個
// CIN_ASSERT( M , 0 , bound_M );
DepthFirstSearchOnTree<bound_N,E,17> dfst{ N , 0 };
list<ll> A_from_child[bound_N+1] = {};
ll B[bound_N];
FOR( n , 0 , N ){
const int& i = dfst.Node( n , true );
const int& j = dfst.Parent( i );
list<ll>& A_from_child_i = A_from_child[i+1];
ll& Bi = B[i] = 0;
while( !A_from_child_i.empty() ){
( Bi += A_from_child_i.front() ) < P ? Bi : Bi -= P;
A_from_child_i.pop_front();
}
( ( Bi *= power_10[length[i]] ) += A[i] * ( dfst.Weight( i ) + 1 ) ) %= P;
A_from_child[j+1].push_back( Bi );
}
FOR( n , 1 , N ){
const int& i = dfst.Node( n );
ll& Bi = B[i];
const int& j = dfst.Parent( i );
( Bi += ( B[j] - ( Bi * power_10[length[j]] + A[j] * ( dfst.Weight( i ) + 1 ) ) ) % P * power_10[length[i]] + A[i] * ( N - dfst.Weight( i ) - 1 ) ) %= P;
}
// DEXPR( int , bound_Q , 100000 , 100 );
// CIN_ASSERT( Q , 1 , bound_Q );
// REPEAT( Q ){
// COUT( N );
// }
// ll guchoku = Guchoku();
ll answer = 0;
FOR( i , 0 , N ){
answer += B[i];
}
// if( answer == guchoku ){
// CERR( answer << " == " << guchoku );
// } else {
// CERR( answer << " != " << guchoku );
// QUIT;
// }
COUT( ( ( answer %= P ) < 0 ? answer += P : answer ) );
FINISH_MAIN;
QUIT;
}