結果
| 問題 |
No.2430 Damage Zone
|
| コンテスト | |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2023-08-27 16:01:42 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 4 ms / 2,000 ms |
| コード長 | 60,686 bytes |
| コンパイル時間 | 24,464 ms |
| コンパイル使用メモリ | 327,360 KB |
| 最終ジャッジ日時 | 2025-02-16 15:08:59 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 28 |
ソースコード
#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 bool searched_library = false; LibrarySearch( searched_library ); if( searched_library ){ 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 SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS )
#define TEST_CASE_NUM( BOUND ) DEXPR( int , bound_T , BOUND , min( BOUND , 100 ) ); int T = 1; if constexpr( bound_T > 1 ){ SET_ASSERT( T , 1 , bound_T ); }
#define START_MAIN REPEAT( T ){ if constexpr( bound_T > 1 ){ CERR( "testcase " << VARIABLE_FOR_REPEAT_T << ":" ); }
#define FINISH_MAIN END_MAIN: CERR( "" ); }
#define QUIT return 0
#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 )
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 ); goto END_MAIN; } else { CERR( ( ANSWER ) << " != " << guchoku ); QUIT; }
#else
#define SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX )
#define RETURN( ANSWER ) COUT( ( ANSWER ) ); goto END_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 ) \
// t以下の値が存在すればその最大値のiterator、存在しなければend()を返す。
template <typename T> inline typename set<T>::iterator MaximumLeq( set<T>& S , const T& t ) { const auto end = S.end(); if( S.empty() ){ return end; } auto itr = S.upper_bound( t ); return itr == end ? S.find( *( S.rbegin() ) ) : itr == S.begin() ? end : --itr; }
// t未満の値が存在すればその最大値のiterator、存在しなければend()を返す。
template <typename T> inline typename set<T>::iterator MaximumLt( set<T>& S , const T& t ) { const auto end = S.end(); if( S.empty() ){ return end; } auto itr = S.lower_bound( t ); return itr == end ? S.find( *( S.rbegin() ) ) : itr == S.begin() ? end : --itr; }
// t以上の値が存在すればその最小値のiterator、存在しなければend()を返す。
template <typename T> inline typename set<T>::iterator MinimumGeq( set<T>& S , const T& t ) { return S.lower_bound( t ); }
// tより大きい値が存在すればその最小値のiterator、存在しなければend()を返す。
template <typename T> inline typename set<T>::iterator MinimumGt( set<T>& S , const T& t ) { return S.upper_bound( t ); }
// 圧縮用
#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( "" ); \
CERR( "問題の区分は以下の中で何番に該当しますか？" ); \
problems = { __VA_ARGS__ }; \
problems_size = problems.size(); \
FOR( i , 0 , problems_size ){ \
CERR( i << ": " << problems[i] ); \
} \
cin >> num; \
CERR( "" ); \
if( num < 0 || num >= problems_size ){ \
CERR( "返答は" << problems_size - 1 << "以下の非負整数にしてください。" ); \
CERR( "終了します。" ); \
CERR( "" ); \
return; \
} \
num_temp = 0; \
#define ASK_YES_NO( QUESTION ) \
CERR( "" ); \
CERR( QUESTION << "[y/n]" ); \
cin >> reply; \
if( reply != "y" && reply != "n" ){ \
CERR( "y/nのいずれかで答えてください。" ); \
CERR( "終了します。" ); \
CERR( "" ); \
return; \
} \
CERR( "" ); \
#define SLS( CLASS ) void CLASS ## LibrarySearch( int& num , int& num_temp , string& reply , vector<string>& problems , int& problems_size )
#define CALL_SLS( CLASS ) CLASS ## LibrarySearch( num , num_temp , reply , problems , problems_size )
SLS( ExplicitExpression );
SLS( ExplicitExpressionUnary );
SLS( ExplicitExpressionMultiary );
SLS( ExplicitExpressionIteration );
SLS( ExplicitExpressionArraySum );
SLS( ExplicitExpressionFunctionOnPermutation );
SLS( ExplicitExpressionFunctionOnTree );
SLS( FunctionOnTree );
SLS( ExplicitExpressionFunctionOnNonTreeGraph );
SLS( ExplicitExpressionOrder );
SLS( ExplicitExpressionProbability );
SLS( ExplicitExpressionOther );
SLS( Maximisation );
SLS( MaximisationFunctionOnAffineSpace );
SLS( MaximisationFunctionOnArray );
SLS( MaximisationSubArraySum );
SLS( MaximisationArrayFunction );
SLS( MaximisationArrayLength );
SLS( MaximisationFunctionOnTree );
SLS( MinimisationMovingCost );
SLS( MaximisationStringMatching );
SLS( MaximisationBipartiteMatching );
SLS( MaximisationProbability );
SLS( Counting );
SLS( CountingExplicitExpression );
SLS( CountingArray );
SLS( CountingSubArray );
SLS( CountingSumFixedSubArray );
SLS( CountingRestrctedSubArray );
SLS( CountingRestrctedContinuousSubArray );
SLS( CountingRestrctedDiscontinuousSubArray );
SLS( CountingRestrctedSubPermutation );
SLS( CountingArbitraryArray );
SLS( CountingSubArrayImage );
SLS( CountingPartitionOfTree );
SLS( CountingString );
SLS( CountingMatchingSubString );
SLS( Solving );
SLS( Query );
SLS( QueryArray );
SLS( QueryGraph );
SLS( Decision );
SLS( DecisionConnectedness );
SLS( DecisionHigherConnectedness );
SLS( DecisionGame );
SLS( DecisionAccessibility );
SLS( DecisionSatisfiability );
SLS( Construction );
void LibrarySearch( bool& searched_library )
{
int num = 0;
vector<string> problems{};
int problems_size = 13;
int num_temp = 0;
string reply{};
ASK_YES_NO( "ライブラリーを探索しますか？" );
if( reply != "y" ){
CERR( "ライブラリーを探索せずに続行します。" );
CERR( "" );
return;
}
searched_library = true;
ASK_NUMBER(
"明示式の計算問題" ,
"最大／最小化問題" ,
"数え上げ問題" ,
"求解問題" ,
"クエリ処理問題" ,
"真偽判定問題" ,
"構築問題"
);
if( num == num_temp++ ){
CALL_SLS( ExplicitExpression );
} else if( num == num_temp++ ){
CALL_SLS( Maximisation );
} else if( num == num_temp++ ){
CALL_SLS( Counting );
} else if( num == num_temp++ ){
CALL_SLS( Solving );
} else if( num == num_temp++ ){
CALL_SLS( Query );
} else if( num == num_temp++ ){
CALL_SLS( Decision );
} else if( num == num_temp++ ){
CALL_SLS( Construction );
}
ASK_YES_NO( "マルチテストケースですか？" );
if( reply == "y" ){
CERR( "テストケースを跨ぐ前計算が可能か否かを優先的に考察しましょう。" );
CERR( "" );
CERR( "テストケース全体でのNの総和に直接上限が与えられている問題では、" );
CERR( "ライブラリーの使用時は配列の初期化が各テストケースに必要となる場合に" );
CERR( "TLEとなる可能性が高いです。" );
CERR( "- 動的配列への置き換え" );
CERR( "- 座標圧縮" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\CoordinateCompress" );
CERR( "を検討しましょう。" );
CERR( "" );
CERR( "配列を手元の環境でデバッグしやすくするためにstaticをつけている場合は" );
CERR( "テストケースを跨いで値が残ってしまわないように注意しましょう。" );
CERR( "" );
}
CERR( "ライブラリー探索は以上です。終了します。" );
CERR( "" );
}
SLS( ExplicitExpression )
{
ASK_YES_NO( "入力は１つの数か、１つの数と法を表す数ですか？" );
if( reply == "y" ){
CALL_SLS( ExplicitExpressionUnary );
} else {
CALL_SLS( ExplicitExpressionMultiary );
}
}
SLS( ExplicitExpressionUnary )
{
CERR( "まずは小さい入力の場合を愚直に計算し、OEISで検索しましょう。" );
CERR( "https://oeis.org/?language=japanese" );
CERR( "" );
CERR( "次に出力の定義と等価な式を考察しましょう。" );
CERR( "- 単調ならば、冪乗や階乗" );
CERR( "- 定義にp進法が使われていれば、各種探索アルゴリズム" );
CERR( "- 入力が素数に近い場合に規則性があれば、p進付値、p進法、" );
CERR( " オイラー関数、約数の個数など" );
CERR( "を検討しましょう。" );
CERR( "" );
CERR( "前計算の候補としては" );
CERR( "- 素数列挙" );
CERR( "- １つまたは複数の整数の約数列挙" );
CERR( "- オイラー関数の値の列挙" );
CERR( "- サブゴールとなる関係式を満たす解の列挙" );
CERR( "を検討しましょう。" );
}
SLS( ExplicitExpressionMultiary )
{
ASK_YES_NO( "関数の反復合成の計算問題ですか？" );
if( reply == "y" ){
CALL_SLS( ExplicitExpressionIteration );
} else {
ASK_NUMBER(
"配列上の関数の総和の計算問題" ,
"順列上の関数の計算問題" ,
"木上の関数の総和の計算問題" ,
"木以外のグラフ上の関数の計算問題" ,
"序数の計算問題" ,
"確率／期待値の計算問題" ,
"その他の明示式の計算問題"
);
if( num == num_temp++ ){
CALL_SLS( ExplicitExpressionArraySum );
} else if( num == num_temp++ ){
CALL_SLS( ExplicitExpressionFunctionOnPermutation );
} else if( num == num_temp++ ){
CALL_SLS( ExplicitExpressionFunctionOnTree );
} else if( num == num_temp++ ){
CALL_SLS( ExplicitExpressionFunctionOnNonTreeGraph );
} else if( num == num_temp++ ){
CALL_SLS( ExplicitExpressionOrder );
} else if( num == num_temp++ ){
CALL_SLS( ExplicitExpressionProbability );
} else if( num == num_temp++ ){
CALL_SLS( ExplicitExpressionOther );
}
}
}
SLS( ExplicitExpressionIteration )
{
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( "を検討しましょう。" );
}
SLS( ExplicitExpressionArraySum )
{
ASK_NUMBER(
"成分を受け取る関数の総和の計算問題" ,
"部分列を受け取る関数の総和の計算問題"
);
if( num == num_temp++ ){
CERR( "成分を受け取る関数fが与えられているとします。" );
CERR( "fが一次式の場合、実質内積と定数の和となります。" );
CERR( "内積は片方の添え字を反転させることで畳み込みに帰着させることができます。" );
CERR( "配列への操作がシフトである場合は繰り返し内積を求めることになるので、" );
CERR( "適当な法での高速フーリエ変換" );
CERR( "\\Mathematics\\Arithmetic\\Mod" );
CERR( "\\Mathematics\\Polynoial" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
ASK_NUMBER(
"連続部分列への分割に関する関数の総和の計算問題" ,
"連続とは限らない部分列への分割に関する関数の総和の計算問題"
);
if( num == num_temp++ ){
CERR( "配列の添字集合は全順序集合なので、木の分割の問題に一般化されます。" );
CALL_SLS( ExplicitExpressionFunctionOnTree );
CERR( "" );
CERR( "更にfが部分列の長さに関する再帰的な構造を持つ場合、全ての連続部分列に" );
CERR( "対しfの値を前計算することを検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "配列の並び換えによって答えが変わらないので、適切にソートしてから" );
CERR( "計算することを検討しましょう。" );
}
}
CERR( "" );
CERR( "入力が大きい場合と小さい場合で解法を変える考察を忘れないようにしましょう。" );
}
SLS( ExplicitExpressionFunctionOnPermutation )
{
CERR( "- 符号そのものの計算問題は" );
CERR( " - O(N log_2 N)やO(N^2)が間に合いそうなら転倒数の計算" );
CERR( " - O(N log_2 N)が間に合わなさそうなら互換表示（O(N)）" );
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( "限らない順列の個数の半分となります。" );
}
SLS( ExplicitExpressionFunctionOnTree )
{
CALL_SLS( FunctionOnTree );
CERR( "" );
CERR( "部分木に関する良い遷移関係を探し、（全方位）木DP" );
CERR( "\\Mathematics\\Geometry\\Graph\\DepthFirstSearch\\Tree" );
CERR( "を検討しましょう。" );
ASK_YES_NO( "fがbit演算である問題ですか？" );
if( reply == "y" ){
CERR( "「Tの各ノードvを根とする部分木でのj桁目のbit状態sの個数dp[v][s][j]」" );
CERR( "を管理するv,s,jに関する動的計画法を検討しましょう。" );
CERR( "これはTが全順序集合でbit演算が1種類なら" );
CERR( "「第i成分で切った部分列でのj桁目のbitがs（=0,1）である個数dp[i][s][j]」" );
CERR( "を管理することに他なりません。" );
CERR( "" );
CERR( "適宜、bitsetや累積和などのデータ構造で高速化しましょう。" );
}
}
SLS( FunctionOnTree )
{
CERR( "木を受け取る関数fが与えられているとします。" );
CERR( "" );
CERR( "木Tの分割Pに対し、Pの各成分pを渡るf(p)の総和をF(P)と置きます。" );
CERR( "Tに根を固定し、深さ優先探索でTの頂点にラベルづけをします。" );
CERR( "" );
CERR( "Pの各成分pに対しpの各頂点のラベルの最小値をD(p)と置き、" );
CERR( "Dについて昇順にPを並べます。" );
CERR( "" );
CERR( "Pの末尾成分pを削除した分割P'が元の木からpを削除した木の分割であり" );
CERR( "F(P)=F(P')+f(p)と表せることに注意しましょう。" );
}
SLS( ExplicitExpressionFunctionOnNonTreeGraph )
{
CERR( "- 部分集合上の関数の計算問題は" );
CERR( " - O(N 2^N)が間に合いそうなら高速ゼータ変換／メビウス変換" );
CERR( " \\Mathematics\\Combinatorial\\ZetaTransform" );
CERR( " - O(N^2)が間に合いそうで要素数にのみ依存するならマーラー変換" );
CERR( " \\Mathematics\\Combinatorial\\ZetaTransform\\MahlerTransform" );
CERR( "- その他の順序集合上の関数の計算問題はゼータ変換／メビウス変換" );
CERR( " \\Mathematics\\Combinatorial\\ZetaTransform" );
CERR( "を検討しましょう。" );
}
SLS( ExplicitExpressionOrder )
{
CERR( "集合Sを何らかの順序でソートした配列aに関する問題で、" );
CERR( "- 与えられた要素sが下から何番目かを答える場合は、非負整数iごとに" );
CERR( " 不等式a[i]<=sを判定する方法を考察し、iに関する二分探索" );
CERR( "- 与えられた非負整数iに対するa[i]を答える場合は、Sの要素sごとに" );
CERR( " 不等式a[i]<=sを判定する方法を考察し、sに関する二分探索" );
CERR( "を検討しましょう。" );
}
SLS( ExplicitExpressionProbability )
{
CERR( "- 確率計算は" );
CERR( " - 余事象や包除原理（高速ゼータ変換／メビウス変換）" );;
CERR( " \\Mathematics\\Combinatorial\\ZetaTransform" );
CERR( " - 同様に確からしい事象の特定" );
CERR( " - ベイズの定理" );
CERR( "- 期待値計算は" );
CERR( " - 上記方法での確率計算" );
CERR( " - 対象を独立な和で表して線形性" );
CERR( "を検討しましょう。" );
}
SLS( ExplicitExpressionOther )
{
CERR( "- 出力の定義と等価な式への変形" );
CERR( " - 和の順序交換" );
CERR( " - 同じ値になる項の纏め上げ" );
CERR( " - 二項展開や積の和典型などの組み合わせ論的解釈" );
CERR( " https://ei1333.hateblo.jp/entry/2021/07/30/144201" );
CERR( "- 和の動く範囲の差分に注目した動的計画法" );
CERR( "を検討しましょう。" );
}
SLS( Maximisation )
{
ASK_NUMBER(
"低次元アフィン空間上の関数の最大／最小化問題" ,
"配列上の関数の最大／最小化問題" ,
"配列の隣接成分間関係式を満たす部分列の最長化問題" ,
"木上の関数の最大／最小化問題" ,
"移動コスト最小化問題" ,
"文字列のマッチングに関する最大／最長化問題" ,
"最大二部マッチング問題" ,
"確率／期待値の最大化問題"
);
if( num == num_temp++ ){
CALL_SLS( MaximisationFunctionOnAffineSpace );
} else if( num == num_temp++ ){
CALL_SLS( MaximisationFunctionOnArray );
} else if( num == num_temp++ ){
CALL_SLS( MaximisationArrayLength );
} else if( num == num_temp++ ){
CALL_SLS( MaximisationFunctionOnTree );
} else if( num == num_temp++ ){
CALL_SLS( MinimisationMovingCost );
} else if( num == num_temp++ ){
CALL_SLS( MaximisationStringMatching );
} else if( num == num_temp++ ){
CALL_SLS( MaximisationBipartiteMatching );
} else if( num == num_temp++ ){
CALL_SLS( MaximisationProbability );
}
}
SLS( MaximisationFunctionOnAffineSpace )
{
ASK_NUMBER(
"凸関数の最小／最大化問題" ,
"可微分関数の最小／最大化問題" ,
"絶対値の最小／最大化問題"
);
if( num == num_temp++ ){
CERR( "三分探索を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "ニュートン法を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "符号を用いて絶対値を外しましょう。" );
CERR( "- 単調な式に帰着できる場合、二分探索" );
CERR( "- 最大化問題の場合、符号パターンの全探策" );
CERR( "- マンハッタン距離などは一次変換" );
CERR( "を検討しましょう。" );
}
CERR( "" );
CERR( "複数のパラメータを決定すべき場合は、サブゴールの式の値を決め打ちましょう。" );
}
SLS( MaximisationFunctionOnArray )
{
ASK_NUMBER(
"問題文または入力で与えられる１つの配列に関する問題" ,
"条件を満たす任意の配列に関する問題"
);
if( num == num_temp++ ){
ASK_NUMBER(
"成分を受け取る関数の部分和の最大化問題" ,
"配列の変更と配列を受け取る関数の合成の最大化問題"
);
if( num == num_temp++ ){
CALL_SLS( MaximisationSubArraySum );
} else if( num == num_temp++ ){
CALL_SLS( MaximisationArrayFunction );
}
} else if( num == num_temp++ ){
CERR( "- 取り得る値が少なく関数が長さに関して再帰的構造を持つ場合は、" );
CERR( " 「長さiの時に可能な値全体または一部の集合dp[i]」" );
CERR( " を管理するiに関する動的計画法" );
CERR( "- 「v以上の値を取り得るか否か」が判定可能である時は" );
CERR( " vに関する二分探索" );
CERR( "を検討しましょう。" );
}
}
SLS( MaximisationSubArraySum )
{
CERR( "項数N、選択回数上限M、価値（和を取る値）上限Vとします。" );
ASK_NUMBER(
"各選択のコスト上限が存在しないか一定の問題" ,
"選択ごとにコストの上限が異なる問題"
);
if( num == num_temp++ ){
CERR( "各選択のコスト上限が存在する場合、その上限以下の項だけを考えましょう。" );
CERR( "コストの総和上限Cとします。C=∞ならば通常のナップサック問題と" );
CERR( "同様の動的計画法で良いので、以下C<∞の場合を考えます。" );
CERR( "- O(2^N)が通りそうならば愚直に全探策" );
CERR( "- O(N 2^{N/2})が通りそうならば半分全列挙" );
CERR( "- コストと価値が等しくO(NV)が通りそうならば[C-V,C+V]での実現可能性を" );
CERR( " 遷移する動的計画法" );
CERR( " https://stackoverflow.com/a/18949218" );
CERR( "- コストと価値が等しくO((N+C)log_2 C)が通りそうならば" );
CERR( " 適当な法での畳み込み（確率的解法）" );
CERR( " \\Mathematics\\Polynomial" );
CERR( "- コストと価値が等しくなくO(C^2)が通りそうならば" );
CERR( " 「コストcの項の価値の最大値v[c]」" );
CERR( " を前計算し" );
CERR( " 「コストの総和がc以下の時の価値の最大値dp[c]」" );
CERR( " を管理するcに関する動的計画法" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "コストの次元をK<=2、n項目のコストをC_nとし、" );
CERR( "m選択目ではC_n[k_m]<=D_mを満たす項nを選べるとします。" );
CERR( "" );
CERR( "項{C_n,n}と選択{k_m,D_m}をそれぞれ辞書式順序でソートし、" );
CERR( "以下の手順で選択を昇順に決定していきましょう。" );
CERR( "- K=1の場合、各選択では可能な選択の中で最大のものを採用しましょう。" );
CERR( "- K=2の場合、各選択では可能な選択の{第2成分,項番号}をsetで管理しつつ" );
CERR( " その中で最大のものを採用しましょう。" );
}
}
SLS( MaximisationArrayFunction )
{
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)で計算できるならば、" );
CERR( " 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( "を検討しましょう。" );
}
SLS( MaximisationArrayLength )
{
CERR( "全順序か疎な半順序かで効率的な実装が違います。" );
CERR( "- 全順序ならば、条件を満たす部分列の長さの最大値をインデックスに持つ" );
CERR( " 配列を用いて、それらの部分列の末尾である項を記録すること" );
CERR( " \\Mathematics\\Combinatorial\\Counting\\IncreasingSubsequence" );
CERR( "- 疎な半順序ならば、条件を満たす部分列の末尾をインデックスに持つ" );
CERR( " 連想配列を用いて、それら部分列の長さの最大値を記録すること" );
CERR( " \\Mathematics\\Combinatorial\\Counting\\IncreasingSubsequence\\Subwalk" );
CERR( "を検討しましょう。" );
}
SLS( MaximisationFunctionOnTree )
{
CALL_SLS( FunctionOnTree );
CERR( "「第i頂点までで切った時のF(P)たちの最大値dp[i]」" );
CERR( "を管理するiに関する動的計画法（O(N^2×fの計算量)）" );
CERR( "を検討しましょう。" );
}
SLS( MinimisationMovingCost )
{
ASK_NUMBER(
"２点最小コスト移動（迷路）問題" ,
"多点最小コスト移動（スタンプラリー）問題"
);
if( num == num_temp++ ){
CERR( "特定の経路を進むと思い込んで考察漏れをする可能性があります。" );
CERR( "なるべく全ての経路を許した探索アルゴリズムを適用した方が無難です。" );
CERR( "- 特定の２点のみを考える場合、BFSやDijkstra" );
CERR( " \\Mathematics\\Geometry\\Graph\\BreadthFirst" );
CERR( " \\Mathematics\\Geometry\\Graph\\Dijkstra" );
CERR( "- 全ての２点の組み合わせを考える場合、" );
CERR( " - 一般のモノイド演算を考えておりO(V^3)が通りそうならば、FloydWarshall" );
CERR( " \\Mathematics\\Geometry\\Graph\\FloydWarshall" );
CERR( " - max演算を考えておりO(E(log_2 E + α(V)))が通りそうならば、UnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "を検討しましょう。" );
CERR( "" );
CERR( "点の座標と最小化すべきコスト以外の数値変化がある場合、最小コスト移動における" );
CERR( "その数値の動く範囲を絞って点の座標との組を頂点とするグラフを検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "HeldKarpや、移動方法を分類するパラメータの全探策などを検討しましょう。" );
}
}
SLS( MaximisationStringMatching )
{
CERR( "基本的には丁寧にループを回して解きましょう。" );
CERR( "- 比較対象が少ない場合、前または後ろから順に探索（貪欲法／動的計画法）" );
CERR( "- ワイルドカードを含む場合、" );
CERR( " - 前または後ろから順に場合分けをしてO(N)で処理できるか" );
CERR( " - 可能な代入方法を絞り込んでO(N)種類に落せるか" );
CERR( "- 比較回数が多い場合、ローリングハッシュ" );
CERR( " \\Utility\\String\\RollingHash" );
CERR( "- 部分回文の最長化をする場合、尺取り法による前計算" );
CERR( " \\Utility\\String\\Palindrome" );
CERR( "- マッチングする部分文字列の最長化をする場合、Zアルゴリズム" );
CERR( " \\Utility\\String\\Z-Algorithm" );
CERR( "- マッチングする文字数の最大化をする場合、文字の種類分の{0,1}値配列に" );
CERR( " 分けて内積の最大化（添え字を反転させて適当な法での畳み込み）" );
CERR( " \\Mathematics\\Arithmetic\\Mod" );
CERR( " \\Mathematics\\Polynomial" );
CERR( "を検討しましょう。" );
}
SLS( MaximisationBipartiteMatching )
{
CERR( "HopcroftKarpや最大流" );
CERR( "\\Mathematics\\Geometry\\Graph\\HopcroftKarp" );
CERR( "を検討しましょう。" );
}
SLS( MaximisationProbability )
{
CERR( "操作／戦略を選んで確率／期待値を最大化する場合、" );
CERR( "被操作対象や可能な操作／戦略のデータなどを状態として定式化し、" );
CERR( "「sを経由する場合の確率／期待値の最大値dp[s]」" );
CERR( "を管理するsに関する動的計画法を検討しましょう。" );
}
SLS( Counting )
{
ASK_NUMBER(
"固定長変数関数で与えられる明示式の数え上げ問題" ,
"配列に関する数え上げ問題" ,
"木の分割の数え上げ問題" ,
"文字列の数え上げ問題"
);
if( num == num_temp++ ){
CALL_SLS( CountingExplicitExpression );
} else if( num == num_temp++ ){
CALL_SLS( CountingArray );
} else if( num == num_temp++ ){
CALL_SLS( CountingPartitionOfTree );
} else if( num == num_temp++ ){
CALL_SLS( CountingString );
}
}
SLS( CountingExplicitExpression )
{
CERR( "- 変数の対称性があれば大小関係を制限した全探策" );
CERR( "- 何らかの約数となるなど動く範囲が狭い変数があればそれらを決め打った全探策" );
CERR( "- 多変数の合成関数で表せる場合は半分全列挙" );
CERR( "を検討しましょう。" );
}
SLS( CountingArray )
{
ASK_NUMBER(
"問題文または入力で与えられる１つの配列に関する問題" ,
"条件を満たす任意の配列に関する問題"
);
if( num == num_temp++ ){
CALL_SLS( CountingSubArray );
} else if( num == num_temp++ ){
CALL_SLS( CountingArbitraryArray );
}
}
SLS( CountingSubArray )
{
ASK_NUMBER(
"配列の成分を受け取る関数の部分和を固定した部分列の数え上げ問題" ,
"配列の隣接成分間関係式を満たす部分列の数え上げ問題"
"配列の部分列から取得位置情報を落とした配列の数え上げ問題"
);
if( num == num_temp++ ){
CALL_SLS( CountingSumFixedSubArray );
} else if( num == num_temp++ ){
CALL_SLS( CountingRestrctedSubArray );
} else if( num == num_temp++ ){
CALL_SLS( CountingSubArrayImage );
}
}
SLS( CountingSumFixedSubArray )
{
CERR( "項数N、コストの総和の上限Cとします。" );
CERR( "- コストと価値が異なりO(2^N)が通りそうならば愚直な２変数多項式乗算" );
CERR( "- コストと価値が等しくO(2^N)が通りそうならば愚直な１変数多項式乗算" );
CERR( "- コストと価値が等しくO(2^{N/2}N)が通りそうならば半分ずつ多項式乗算を" );
CERR( " して最後にそれらの積の１係数のみの計算" );
CERR( "- コストと価値が等しくCが10^5オーダーで法が与えられていてO((N+C)log_2 C)が" );
CERR( " 通りそうならば適当な法での高速フーリエ変換" );
CERR( " \\Mathematics\\Arithmetic\\Mod" );
CERR( " \\Mathematics\\Polynomial" );
CERR( "を検討しましょう。" );
}
SLS( CountingRestrctedSubArray )
{
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++ ){
CALL_SLS( CountingRestrctedContinuousSubArray );
} else if( num == num_temp++ ){
CALL_SLS( CountingRestrctedDiscontinuousSubArray );
} else if( num == num_temp++ ){
CALL_SLS( CountingRestrctedSubPermutation );
}
CERR( "を検討しましょう。" );
CERR( "" );
CERR( "特にR_l(B)たちがgcdやmaxなどの羃等演算に関する等式で与えられる場合は、" );
CERR( "不等式の方が扱いやすいのでゼータ変換／メビウス変換" );
CERR( "\\Mathematics\\Combinatorial\\ZetaTransform" );
CERR( "を検討しましょう。" );
}
SLS( CountingRestrctedContinuousSubArray )
{
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たちの読み替え" );
CERR( "を検討しましょう。" );
}
SLS( CountingRestrctedDiscontinuousSubArray )
{
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" );
CERR( "を検討しましょう。" );
}
SLS( CountingRestrctedSubPermutation )
{
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( "を検討しましょう。" );
}
SLS( CountingArbitraryArray )
{
ASK_NUMBER(
"配列を受け取る関数の値の数え上げ問題" ,
"隣接成分間関係式を満たす配列の数え上げ問題"
);
if( num == num_temp++ ){
CERR( "- 配列の種類が少ない場合は、全ての配列に対する関数の値の前計算" );
CERR( "- 取り得る値が少なく関数が長さに関して再帰的構造を持つ場合は、" );
CERR( " 「長さiの時に値vである配列の総数dp[i][v]」" );
CERR( " を管理するi,vに関する動的計画法" );
} else if( num == num_temp++ ){
CERR( "- いくつかの条件の重ね合わせの時は包除原理" );
CERR( "- 全順序の場合は数の分割方法などへの翻訳" );
CERR( "- 疎な半順序の場合はグラフの前計算" );
}
CERR( "を検討しましょう。" );
}
SLS( CountingSubArrayImage )
{
CERR( "入力で与えられる配列をAと置きます。" );
CERR( "配列として等しいAの部分列のうち辞書式順序最小のものを数え上げる" );
CERR( "部分列DPを検討しましょう。具体的には" );
CERR( "「末尾が第i成分由来で辞書順最小なAの部分列の個数dp[i]」" );
CERR( "「s=A[j]を満たすj<iの最大値last[i][s]」" );
CERR( "の２つを管理するiに関する動的計画法を検討しましょう。" );
CERR( "" );
CERR( "適宜、累積和などのデータ構造で高速化しましょう。" );
}
SLS( CountingPartitionOfTree )
{
CALL_SLS( FunctionOnTree );
CERR( "F(P)が固定された時のPの数え上げ問題は" );
CERR( "「第i成分までで切った時のF(P)=vを満たすPの個数dp[i][v]」" );
CERR( "を管理するi,vに関する動的計画法（O(N^2 v_max×fの計算量)）" );
CERR( "を検討しましょう。" );
}
SLS( CountingString )
{
ASK_NUMBER(
"部分文字列から取得位置情報を落とした文字列全体の数え上げ問題" ,
"マッチングに関する性質を満たす部分文字列の数え上げ問題"
);
if( num == num_temp++ ){
CERR( "文字列を文字の配列とみなすことで、配列の問題に帰着させることができます。" );
CALL_SLS( CountingSubArrayImage );
} else if( num == num_temp++ ){
CALL_SLS( CountingMatchingSubString );
}
}
SLS( CountingMatchingSubString )
{
CERR( "- 自分とマッチングする部分文字列の数え上げ問題はZアルゴリズム" );
CERR( " \\Utility\\String\\Z-Algorithm" );
CERR( "- 回文である部分文字列の数え上げ問題は" );
CERR( " - O(N^2)が通る場合、尺取り法による前計算" );
CERR( " \\Utility\\String\\Palindrome" );
CERR( " - O(N^2)が通らない場合、Manacherのアルゴリズムやローリングハッシュで前計算" );
CERR( " https://snuke.hatenablog.com/entry/2014/12/02/235837" );
CERR( " \\Utility\\String\\RollingHash" );
CERR( "を検討しましょう。" );
}
SLS( Solving )
{
CERR( "- 単調関数は二分探索" );
CERR( "- 可微分関数はニュートン法" );
CERR( "- 一次関数は掃き出し法" );
CERR( "を検討しましょう。" );
}
SLS( Query )
{
ASK_NUMBER(
"配列の問題" ,
"グラフの問題"
);
if( num == num_temp++ ){
CALL_SLS( QueryArray );
} else if( num == num_temp++ ){
CALL_SLS( QueryGraph );
}
}
SLS( QueryArray )
{
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)で処理できます。" );
}
}
SLS( QueryGraph )
{
ASK_YES_NO( "代数構造を扱う問題ですか？" );
if( reply == "yes" ){
CERR( "- 可換群構造に関する加算／全更新後の一点取得が必要ならば階差数列" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\Tree\\DifferenceSeqeuence" );
} else {
CERR( "深さ優先探索や動的木やUnionFind" );
CERR( "\\Mathematics\\Geometry\\Graph\\DepthFirst\\Tree" );
CERR( "\\Utility\\VLTree" );
CERR( "\\Utility\\VLTree\\UnionFndForest" );
}
CERR( "を検討しましょう。" );
}
SLS( Decision )
{
ASK_NUMBER(
"0次連結性判定問題" ,
"高次連結性判定問題" ,
"勝敗判定問題" ,
"到達可能性問題" ,
"充足可能性問題"
);
if( num == num_temp++ ){
CALL_SLS( DecisionConnectedness );
} else if( num == num_temp++ ){
CALL_SLS( DecisionHigherConnectedness );
} else if( num == num_temp++ ){
CALL_SLS( DecisionGame );
} else if( num == num_temp++ ){
CALL_SLS( DecisionAccessibility );
} else if( num == num_temp++ ){
CALL_SLS( DecisionSatisfiability );
}
}
SLS( DecisionConnectedness )
{
CERR( "幅優先探索やUnionFind" );
CERR( "\\Mathematics\\Geometry\\Graph\\BreadthFirst" );
CERR( "\\Utility\\VLTree\\UnionFindForest" );
CERR( "を検討しましょう。" );
CERR( "" );
}
SLS( DecisionHigherConnectedness )
{
CERR( "- 強連結性判定は深さ優先探索" );
CERR( " \\Mathematics\\Geometry\\Graph\\DepthFirst" );
CERR( "- 高次ホモロジー計算は適当な法での掃き出し法" );
CERR( "を検討しましょう。" );
}
SLS( DecisionGame )
{
CERR( "ゲームの和に分解できる場合は最小単位で考察をし、グランディ数を実装しましょう。" );
CERR( "これ以上分解できないゲームには整礎構造を探し、順序数の小さい順に実験をしましょう。" );
}
SLS( DecisionAccessibility )
{
ASK_YES_NO( "矩形領域の到達可能性問題ですか？" );
if( reply == "yes" ){
CERR( "迷路の攻略可能性は" );
CERR( "- スタートとゴールが同一の弧状連結成分に属すこと" );
CERR( "- スタートとゴールを分断する壁のパスの非存在性" );
CERR( "などに翻訳しグラフ上の最小コスト移動問題に帰着させましょう。" );
} else {
CERR( "適切なグラフ上の最小コスト移動問題に帰着させましょう。" );
CALL_SLS( MinimisationMovingCost );
}
CERR( "" );
}
SLS( DecisionSatisfiability )
{
ASK_NUMBER(
"命題論理の充足性判定問題" ,
"二部グラフの充足可能性問題"
);
if( num == num_temp++ ){
CERR( "各命題変数の真理値を頂点とするグラフを考え連結性判定に帰着させて" );
CALL_SLS( DecisionConnectedness );
CERR( "" );
CERR( "区間処理による真理値更新は各種代数的データ構造を用いましょう。" );
SLS( QueryArray );
} else if( num == num_temp++ ){
CERR( "完全二部マッチング判定は最大二部マッチングに帰着させて" );
SLS( MaximisationBipartiteMatching );
}
}
SLS( Construction )
{
ASK_NUMBER(
"数や配列や文字列の構築" ,
"経路の構築" ,
"戦略の構築" ,
"ソースコードの構築"
);
if( num == num_temp++ ){
CERR( "p進法を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "可能な経路の定めるグラフの問題に帰着させましょう。" );
CALL_SLS( DecisionAccessibility );
} else if( num == num_temp++ ){
CERR( "ゲームの問題に帰着させましょう。" );
CALL_SLS( DecisionGame );
} else if( num == num_temp++ ){
CERR( "正解を出力をするソースコードを提出しましょう。" );
}
}
inline CEXPR( ll , P , 998244353 );
// inline CEXPR( ll , P , 1000000007 );
// // inline CEXPR( int , bound_N , 10 );
// inline DEXPR( int , bound_N , 100000 , 100 ); // 0が5個
// // inline CEXPR( int , bound_N , 1000000000 ); // 0が9個
// // inline CEXPR( ll , bound_N , 1000000000000000000 ); // 0が18個
// TYPE_OF( bound_N ) N;
// // inline CEXPR( TYPE_OF( bound_N ) , bound_M , bound_N );
// // inline CEXPR( int , bound_M , 10 );
// inline DEXPR( int , bound_M , 100000 , 100 ); // 0が5個
// // inline CEXPR( int , bound_M , 1000000000 ); // 0が9個
// // inline CEXPR( ll , bound_M , 1000000000000000000 ); // 0が18個
// TYPE_OF( bound_M ) M;
inline DEXPR( int , bound_H , 1000 , 10 );
// inline DEXPR( int , bound_H , 100000 , 10 ); // 0が5個
// inline CEXPR( int , bound_H , 1000000000 ); // 0が9個
inline CEXPR( int , bound_W , bound_H );
static_assert( ll( bound_H ) * bound_W < ll( 1 ) << 31 );
inline CEXPR( int , bound_HW , bound_H * bound_W );
// CEXPR( int , bound_HW , 100000 ); // 0が5個
// CEXPR( int , bound_HW , 1000000000 ); // 0が5個
int H , W , H_minus , W_minus , HW;
// inline pair<int,int> EnumHW( const int& v ) { return { v / W , v % W }; }
// inline int EnumHW_inv( const int& h , const int& w ) { return h * W + w; }
// inline void SetEdgeOnGrid( const string& Si , const int& i , list<int> ( &e )[bound_HW] , const char& walkable = '.' ){FOR(j,0,W){if(Si[j]==walkable){int v = EnumHW_inv(i,j);if(i>0){e[EnumHW_inv(i-1,j)].push_back(v);}if(i+1<H){e[EnumHW_inv(i+1,j)].push_back(v);}if(j>0){e[EnumHW_inv(i,j-1)].push_back(v);}if(j+1<W){e[EnumHW_inv(i,j+1)].push_back(v);}}}}
// const string direction[4] = {"U","R","D","L"};
// inline int DirectionNumberOnGrid( const int& i , const int& j , const int& k , const int& h ){return i<k?2:i>k?0:j<h?1:j>h?3:(assert(false),-1);}
// inline int DirectionNumberOnGrid( const int& v , const int& w ){auto [i,j]=EnumHW(v);auto [k,h]=EnumHW(w);return DirectionNumberOnGrid(i,j,k,h);}
// inline int ReverseDirectionNumberOnGrid( const int& n ){assert(0<=n&&n<4);return(n+2)%4;}
// bool open[bound_H+1][bound_W+1]={};
// inline void SetWallOnGrid( const string& Si , const int& i , bool ( &open )[bound_H+1][bound_W+1] , const char& walkable = '.' ){bool(&open_i)[bound_W+1]=open[i];FOR(j,0,W){open_i[j]=Si[j]==walkable?true:(assert(Si[j]=='#'),false);}}
// using path_type = int;
// // using path_type = pair<int,ll>;
// list<path_type> e[bound_N];
// // list<path_type> e[bound_HW];
// list<path_type> E( const int& i )
// {
// list<path_type> answer = e[i];
// // 入力によらない処理
// return answer;
// }
// template <typename T> inline T add( const T& t0 , const T& t1 ) { return t0 + t1; }
// template <typename T> inline const T& zero() { static const T z = 0; return z; }
// template <typename T> inline T add_inv( const T& t ) { return -t; }
// template <typename T> inline T multiply( const T& t0 , const T& t1 ) { return t0 * t1; }
// template <typename T> inline const T& one() { static const T o = 1; return o; }
// inline int id( const int& v ) { return v; }
int main()
{
UNTIE;
LIBRARY_SEARCH;
TEST_CASE_NUM( 1 );
START_MAIN;
// // CIN( ll , N );
// SET_ASSERT( N , 1 , bound_N );
// // CIN( ll , M );
// SET_ASSERT( M , 1 , bound_M );
// // CIN( ll , K );
// CIN( string , S );
// CIN( string , T );
SET_ASSERT( H , 1 , bound_H );
SET_ASSERT( W , 1 , bound_W );
CIN( ll , K );
H_minus = H - 1;
W_minus = W - 1;
HW = H * W;
assert( HW <= bound_HW );
ll count[2][W][K];
int i_prev = 1;
int i_curr = 0;
string S_prev;
FOR( i , 0 , H ){
CIN( string , S_curr );
auto& count_curr = count[i_curr];
auto& count_prev = count[i_prev];
FOR( j , 0 , W ){
auto& count_curr_j = count_curr[j];
auto& count_prev_j = count_prev[j];
FOR( k , 0 , K ){
count_curr_j[k] = i == 0 && j == 0 && k == 0 ? 1 : 0;
}
if( i > 0 ){
const char& c = S_prev[j];
if( c == '.' ){
FOR( k , 0 , K ){
auto& count_curr_jk = count_curr_j[k];
( count_curr_jk += count_prev_j[k] ) < P ? count_curr_jk : count_curr_jk -= P;
}
} else if( c == 'o' ){
FOR( k , 1 , K ){
auto& count_curr_jk = count_curr_j[k];
( count_curr_jk += count_prev_j[k-1] ) < P ? count_curr_jk : count_curr_jk -= P;
}
}
}
if( j > 0 ){
const char& c = S_curr[j-1];
auto& count_curr_j_minus = count_curr[j-1];
if( c == '.' ){
FOR( k , 0 , K ){
auto& count_curr_jk = count_curr_j[k];
( count_curr_jk += count_curr_j_minus[k] ) < P ? count_curr_jk : count_curr_jk -= P;
}
} else if( c == 'o' ){
FOR( k , 1 , K ){
auto& count_curr_jk = count_curr_j[k];
( count_curr_jk += count_curr_j_minus[k-1] ) < P ? count_curr_jk : count_curr_jk -= P;
}
}
}
}
S_prev = move( S_curr );
swap( i_curr , i_prev );
}
// ll A[N];
// ll B[N];
// // ll A[bound_N];
// // ll B[bound_N];
// FOR( i , 0 , N ){
// cin >> A[i];
// cin >> B[i];
// }
// FOR( i , 0 , M ){
// CIN_ASSERT( ui , 1 , N );
// CIN_ASSERT( vi , 1 , N );
// ui--;
// vi--;
// e[ui].push_back( vi );
// e[vi].push_back( ui );
// }
// CIN( int , Q );
// // DEXPR( int , bound_Q , 100000 , 100 );
// // CIN_ASSERT( Q , 1 , bound_Q );
// REPEAT( Q ){
// COUT( N );
// }
// // ll guchoku = Guchoku();
ll answer = 0;
auto& count_last = count[i_prev][W-1];
FOR( k , 0 , K ){
( answer += count_last[k] ) < P ? answer : answer -= P;
}
// // COUT( ( answer ) );
RETURN( answer );
FINISH_MAIN;
QUIT;
}