結果
問題 | No.2975 単調増加部分積 |
ユーザー | 👑 p-adic |
提出日時 | 2023-08-22 09:55:39 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 3,501 bytes |
コンパイル時間 | 3,434 ms |
コンパイル使用メモリ | 219,144 KB |
実行使用メモリ | 723,868 KB |
最終ジャッジ日時 | 2024-12-16 05:48:30 |
合計ジャッジ時間 | 13,383 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 3 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 3 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 2 ms
5,248 KB |
testcase_13 | AC | 15 ms
7,808 KB |
testcase_14 | AC | 4 ms
5,248 KB |
testcase_15 | AC | 24 ms
11,264 KB |
testcase_16 | AC | 3 ms
5,248 KB |
testcase_17 | AC | 5 ms
5,248 KB |
testcase_18 | AC | 23 ms
11,136 KB |
testcase_19 | AC | 203 ms
78,592 KB |
testcase_20 | MLE | - |
testcase_21 | MLE | - |
testcase_22 | MLE | - |
testcase_23 | MLE | - |
ソースコード
// 誤解法(非コンパイル畤定数サイズのメモリ確保による空間計算量O(NM)解)チェック2 #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 ) ) #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 ) ) #endif #include <bits/stdc++.h> using namespace std; using ll = long long; #define MAIN main #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 SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX ) #define CIN_ASSERT( A , MIN , MAX ) TYPE_OF( MAX ) A; SET_ASSERT( A , MIN , MAX ) #define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) #define QUIT return 0 #define RETURN( ANSWER ) COUT( ( ANSWER ) ); QUIT #ifdef DEBUG inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); } #endif #define FACTORIAL_MOD( ANSWER , ANSWER_INV , INVERSE , MAX_INDEX , CONSTEXPR_LENGTH , MODULO ) \ ll ANSWER[CONSTEXPR_LENGTH]; \ ll ANSWER_INV[CONSTEXPR_LENGTH]; \ 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 ); \ } \ } \ int MAIN() { UNTIE; DEXPR( int , bound_N , 9600 , 100 ); CIN_ASSERT( N , 1 , bound_N ); CIN_ASSERT( M , 1 , N ); CEXPR( int , bound_P , 1000000000 ); // 0が9個 CIN_ASSERT( P , N + 1 , bound_P ); FACTORIAL_MOD( factorial , factorial_inv , inv , N , N + 1 , P ); ll Pi[M+1][N+1]; FOREQ( j , 1 , M ){ ll ( &Pi_j )[N+1] = Pi[j]; Pi_j[0] = 0; if( j == 1 ){ FOREQ( n , 1 , N ){ Pi_j[n] = n * ( n + 1 ) / 2 % P; } } else { ll ( &Pi_j_minus )[N+1] = Pi[j-1]; FOREQ( n , 1 , N ){ Pi_j[n] = ( Pi_j[n-1] + Pi_j_minus[n-1] * n ) % P; } } } ll answer = 0; FOREQ( j , 1 , M ){ answer += Pi[j][N] * factorial_inv[j] % P * factorial_inv[M-j] % P * factorial[N-j] % P; } RETURN( answer % P * factorial[M] % P * factorial_inv[N] % P ); }