結果

問題 No.2120 場合の数の下８桁
コンテスト
ユーザー 👑 p-adic
提出日時 2022-08-06 14:11:00
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 579 ms / 2,000 ms
コード長 3,958 bytes
コンパイル時間 662 ms
コンパイル使用メモリ 74,588 KB
最終ジャッジ日時 2025-01-30 19:01:24
ジャッジサーバーID
（参考情報） 		judge1 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;

}
0