結果
問題 | No.2120 場合の数の下8桁 |
ユーザー | 👑 p-adic |
提出日時 | 2022-08-06 14:11:00 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 549 ms / 2,000 ms |
コード長 | 3,958 bytes |
コンパイル時間 | 757 ms |
コンパイル使用メモリ | 75,392 KB |
実行使用メモリ | 6,656 KB |
最終ジャッジ日時 | 2024-09-16 10:02:52 |
合計ジャッジ時間 | 3,172 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge6 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 14 ms
6,656 KB |
testcase_01 | AC | 16 ms
6,528 KB |
testcase_02 | AC | 15 ms
6,656 KB |
testcase_03 | AC | 14 ms
6,528 KB |
testcase_04 | AC | 15 ms
6,656 KB |
testcase_05 | AC | 15 ms
6,656 KB |
testcase_06 | AC | 14 ms
6,400 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 14 ms
6,656 KB |
testcase_10 | AC | 14 ms
6,656 KB |
testcase_11 | AC | 14 ms
6,656 KB |
testcase_12 | AC | 15 ms
6,656 KB |
testcase_13 | AC | 20 ms
6,656 KB |
testcase_14 | AC | 23 ms
6,528 KB |
testcase_15 | AC | 236 ms
6,656 KB |
testcase_16 | AC | 16 ms
6,528 KB |
testcase_17 | AC | 547 ms
6,656 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 549 ms
6,656 KB |
ソースコード
#include <iostream> #include <list> #include <vector> #include <string> #include <stdio.h> #include <stdint.h> using namespace std; using ll = long long; static inline constexpr const ll MODULO2 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2; static inline constexpr const ll MODULO5 = 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5; static inline constexpr const ll MODULO10 = MODULO2 * MODULO5; ll Solve( const ll& M , const ll& N ); int main() { ll M; ll N; cin >> M; cin >> N; const ll answer = Solve( M , N ); const string answer_str = to_string( MODULO10 + answer ).substr( 1 ); cout << answer_str << endl; return 0; } void ChineseReminderTheorem( ll& answer , const ll& c0 , const ll& c1 ) noexcept; ll Solve( const ll& M , const ll& N ) { if( M < N ){ return 0; } const ll N_minus = M - N; if( N > N_minus ){ return Solve( M , N_minus ); } constexpr const ll prime[2] = { 2 , 5 }; constexpr const ll MODULO[2] = { MODULO2 , MODULO5 }; // 環境依存でsegmentation fault ll inv2[ MODULO2 ] = {}; ll inv5[ MODULO5 ] = {}; ll* const inv[2] = { inv2 , inv5 }; for( ll i = 0 ; i < 2 ; i++ ){ const ll& prime_i = prime[i]; const ll& MODULO_i = MODULO[i]; ll* const& inv_i = inv[i]; inv_i[1] = 1; for( ll j = 2 ; j < MODULO_i ; j++ ){ if( j % prime_i != 0 ){ // gcd( prime_i , j ) == 1かつj != 1よりj_sub != 0である。 const ll j_sub = MODULO_i % j; const ll& j_sub_inv = inv_i[ j_sub ]; if( j_sub_inv == 0 ){ // j_sub != 0よりj_sub_minus < jである。 const ll j_sub_minus = j - j_sub; // gcd( prime_i , j ) == 1かつj == j_sub + j_sub_minusかつ // gcd( prime_i , j_sub ) != 1よりgcd( prime_i , j_sub_minus ) == 1である。 const ll& j_sub_minus_inv = inv_i[ j_sub_minus ]; inv_i[j] = ( j_sub_minus_inv * ( ( MODULO_i / j ) + 1 ) ) % MODULO_i; } else { inv_i[j] = MODULO_i - ( ( j_sub_inv * ( MODULO_i / j ) ) % MODULO_i ); } } } } ll e[2] = {}; ll c[2] = { 1 , 1 }; ll m = M; ll n = 1; while( n <= N ){ ll m_copy = m; ll n_copy = n; for( ll i = 0 ; i < 2 ; i++ ){ const ll& prime_i = prime[i]; ll& e_i = e[i]; while( m_copy % prime_i == 0 ){ e_i++; m_copy /= prime_i; } while( n_copy % prime_i == 0 ){ e_i--; n_copy /= prime_i; } } for( ll i = 0 ; i < 2 ; i++ ){ const ll& MODULO_i = MODULO[i]; ll* const inv_i = inv[i]; const ll n_copy_i = n_copy % MODULO_i; ll& n_inv_i = inv_i[ n_copy_i ]; ll& c_i = c[i]; const ll d = ( m_copy * n_inv_i ) % MODULO_i; c_i = ( c_i * d ) % MODULO_i; } n++; m--; } ll answer; ChineseReminderTheorem( answer , c[0] , c[1] ); for( ll i = 0 ; i < 2 ; i++ ){ const ll& prime_i = prime[i]; const ll& e_i = e[i]; for( ll j = 0 ; j < e_i ; j++ ){ answer = ( answer * prime_i ) % MODULO10; } } return answer; } void ChineseReminderTheorem( ll& answer , const ll& c0 , const ll& c1 ) noexcept { // ユークリッドの互除法 // MODULO2 = 256 | MODULO5 = 390625 // 256 | 390625 - 256 * 1525 = 225 // 256 - 225 * 1 = 31 | 225 // 31 | 225 - 31 * 7 = 8 // 31 - 8 * 3 = 7 | 8 // 7 | 8 - 7 * 1 = 1 // 単位の分割 // 1 // = 8 - 7 * 1 = 8 * 1 + 7 * ( -1 ) // = 8 * 1 + ( 31 - 8 * 3 ) * ( -1 ) = 8 * 4 + 31 * ( -1 ) // = ( 225 - 31 * 7 ) * 4 + 31 * ( -1 ) = 225 * 4 + 31 * ( -29 ) // = 225 * 4 + ( 256 - 225 * 1 ) * ( -29 ) = 225 * 33 + 256 * ( -29 ) // = ( 390625 - 256 * 1525 ) * 33 + 256 * ( -29 ) = 390625 * 33 + 256 * ( -50354 ) // = MODULO2 * ( -50354 ) + MODULO5 * 33; answer = c0 * MODULO5 * 33 - c1 * MODULO2 * 50354; if( answer >= 0 ){ answer %= MODULO10; } else { const ll answer_minus = ( -answer ) % MODULO10; if( answer_minus == 0 ){ answer = 0; } else { answer = MODULO10 - answer_minus; } } return; }