#834794 (C++17) No.2273 一点乗除区間積

提出ソース

結果

問題	No.2273 一点乗除区間積
ユーザー	👑 p-adic
提出日時	2023-01-21 14:39:10
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	713 ms / 5,000 ms
コード長	8,721 bytes
コンパイル時間	1,937 ms
コンパイル使用メモリ	98,680 KB
実行使用メモリ	20,736 KB
最終ジャッジ日時	2024-06-23 22:43:28
合計ジャッジ時間	7,206 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	11 ms 11,136 KB
testcase_01	AC	10 ms 11,264 KB
testcase_02	AC	9 ms 11,116 KB
testcase_03	AC	8 ms 11,264 KB
testcase_04	AC	11 ms 11,264 KB
testcase_05	AC	11 ms 11,392 KB
testcase_06	AC	9 ms 11,136 KB
testcase_07	AC	9 ms 11,248 KB
testcase_08	AC	8 ms 11,136 KB
testcase_09	AC	8 ms 11,112 KB
testcase_10	AC	9 ms 11,284 KB
testcase_11	AC	11 ms 11,264 KB
testcase_12	AC	9 ms 11,252 KB
testcase_13	AC	9 ms 11,392 KB
testcase_14	AC	8 ms 11,260 KB
testcase_15	AC	8 ms 11,264 KB
testcase_16	AC	23 ms 11,264 KB
testcase_17	AC	22 ms 11,264 KB
testcase_18	AC	246 ms 11,392 KB
testcase_19	AC	207 ms 14,208 KB
testcase_20	AC	512 ms 17,536 KB
testcase_21	AC	713 ms 20,736 KB
testcase_22	AC	535 ms 17,536 KB
testcase_23	AC	527 ms 17,404 KB
testcase_24	AC	481 ms 17,492 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma GCC optimize ( "O3" )
#pragma GCC optimize( "unroll-loops" )
#pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdint.h>
#include <cassert>
#include <vector>
using namespace std;

using ll = long long;

#define MAIN main
#define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) 
#define CEXPR( LL , BOUND , VALUE ) constexpr const LL BOUND = VALUE 
#define CIN( LL , A ) LL A; cin >> A 
#define ASSERT( A , MIN , MAX ) assert( MIN <= A && A <= MAX ) 
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX ) 
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) 
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) 
#define QUIT return 0 
#define COUT( ANSWER ) cout << ( ANSWER ) << "\n"; 
#define RETURN( ANSWER ) COUT( ANSWER ); QUIT 

template <typename T> inline T Residue( const T& a , const T& p ){ return a >= 0 ? a % p : p - 1 - ( ( - ( a + 1 ) ) % p ); }

template <typename INT>
void SetPrimeFactorisation( const INT& n , vector<INT>& P , vector<INT>& exponent )
{

  INT n_copy = n;
  INT p = 2;

  if( n_copy % p == 0 ){

    P.push_back( p );
    exponent.push_back( 1 );
    INT& exponent_back = exponent.back();
    n_copy /= p;
    
    while( n_copy % p == 0 ){

      exponent_back++;
      n_copy /= p;
      
    }

  }

  p++;

  while( p * p <= n_copy ){

    if( n_copy % p == 0 ){

      P.push_back( p );
      exponent.push_back( 1 );
      INT& exponent_back = exponent.back();
      n_copy /= p;
    
      while( n_copy % p == 0 ){

	exponent_back++;
	n_copy /= p;
      
      }

    }

    p += 2;

  }

  if( n_copy != 1 ){

    P.push_back( n_copy );
    exponent.push_back( 1 );
    
  }
  
  return;
  
}

template <typename INT>
INT EulerFunction( const INT& n , vector<INT>& P , vector<INT>& exponent )
{

  SetPrimeFactorisation( n , P , exponent );
  INT answer = n;
  INT size = P.size();

  for( INT i = 0 ; i < size ; i++ ){

    const INT& P_i = P[i];
    answer -= answer / P_i;
    
  }

  return answer;

}

class MG
{
public:
  // 法B
  static ll g_B;
  // Bの素因数
  static vector<int> g_prime;
  // Bの素因数の指数
  static vector<int> g_exponent;
  // g_primeの長さ
  static int g_size;
  // Bのオイラー関数引く1;
  static ll g_euler_minus;
  // 単位元
  static MG g_e;
  
  // 乗法群(Z/BZ)^xの元
  ll m_n;
  // Bの素因数の生成する乗法群の元
  vector<int> m_factor;
  // 0が形式的に生成する自由群の元
  int m_zero;
  inline MG() : m_n() , m_factor() , m_zero() {}
  inline MG( const MG& n ) : m_n( n.m_n ) , m_factor( n.m_factor ) , m_zero( n.m_zero ) {}
  inline MG( MG&& n ) : m_n( move( n.m_n ) ) , m_factor( move( n.m_factor ) ) , m_zero( move( n.m_zero ) ) {}
  inline MG( ll&& n ) : m_n( move( n ) ) , m_factor( g_size ) , m_zero() { if( m_n == 0 ){ m_n = 1; m_zero++; } else { FOR( i , 0 , g_size ){ int& prime_i = g_prime[i]; int& factor_i = m_factor[i]; while( m_n % prime_i == 0 ){ m_n /= prime_i; factor_i++; } } m_n = Residue( m_n , MG::g_B ); } }
  inline MG& operator=( const MG& n ) { m_n = n.m_n; m_factor = n.m_factor; m_zero = n.m_zero; return *this; }  
  inline MG& operator=( MG&& n ) { m_n = move( n.m_n ); m_factor = move( n.m_factor ); m_zero = move( n.m_zero ); return *this; }  
};

ll MG::g_B{};
vector<int> MG::g_prime{};
vector<int> MG::g_exponent{};
int MG::g_size{};
ll MG::g_euler_minus{ 1 };
MG MG::g_e{};

// 乗法
inline MG op( const MG& n0 , const MG& n1 ) { MG answer{ n0 }; if( ! n0.m_factor.empty() && ! n1.m_factor.empty() ){ ( answer.m_n *= n1.m_n ) %= MG::g_B; FOR( i , 0 , MG::g_size ){ answer.m_factor[i] += n1.m_factor[i]; }; answer.m_zero += n1.m_zero; } return answer; }
// 単位元
inline const MG& e() { return MG::g_e; }
// 逆元
inline MG inv( const MG& n ) { MG answer{ n }; answer.m_n = 1; ll power = n.m_n; ll exponent = MG::g_euler_minus; while( exponent != 0 ){ if( ( exponent & 1 ) == 1 ){ ( answer.m_n *= power ) %= MG::g_B; } ( power *= power ) %= MG::g_B; exponent >>= 1; } FOR( i , 0 , MG::g_size ){ answer.m_factor[i] *= -1; } answer.m_zero *= -1; return answer; }

#define TEMPLETE_ARGUMENTS_FOR_BIT typename T , T m_T(const T&,const T&) , const T& e_T() , T i_T(const T&) , int N

// 可換群(T,m_T:T^2->T,e_T:1->T,i_T:T->T)と非負整数Nをパラメータとする。
// ただしi_Tを使うのはSetとIntervalSumのみなので、
// AddとInitialSegmentSumしか使わない場合は
// i_Tを好きに設定して(T,m_T,e_T)をモノイドとして良い。
template <TEMPLETE_ARGUMENTS_FOR_BIT>
class AbstractBIT
{
private:
  T m_fenwick[N + 1];
  
public:
  static const T& g_e;

  inline AbstractBIT();
  AbstractBIT( const T ( & a )[N] );

  inline void Set( const int& i , const T& n );

  inline AbstractBIT<T,m_T,e_T,i_T,N>& operator+=( const T ( & a )[N] );
  void Add( const int& i , const T& n );

  T InitialSegmentSum( const int& i_final );
  inline T IntervalSum( const int& i_start , const int& i_final );
  
};


template <TEMPLETE_ARGUMENTS_FOR_BIT> inline const T& AbstractBIT<T,m_T,e_T,i_T,N>::g_e = e_T();

template <TEMPLETE_ARGUMENTS_FOR_BIT> inline AbstractBIT<T,m_T,e_T,i_T,N>::AbstractBIT() : m_fenwick() { const T& e = g_e; for( int i = 0 ; i <= N ; i++ ){ m_fenwick[i] = e; } }
template <TEMPLETE_ARGUMENTS_FOR_BIT>
AbstractBIT<T,m_T,e_T,i_T,N>::AbstractBIT( const T ( & a )[N] ) : m_fenwick()
{

  for( int j = 1 ; j <= N ; j++ ){

    T& fenwick_j = m_fenwick[j];
    int i = j - 1;
    fenwick_j = a[i];
    int i_lim = j - ( j & -j );

    while( i != i_lim ){

      fenwick_j = m_T( fenwick_j , m_fenwick[i] );
      i -= ( i & -i );

    }

  }

}

template <TEMPLETE_ARGUMENTS_FOR_BIT> inline void AbstractBIT<T,m_T,e_T,i_T,N>::Set( const int& i , const T& n ) { Add( i , m_T( i_T( IntervalSum( i , i ) ) , n ) ); }

template <TEMPLETE_ARGUMENTS_FOR_BIT> inline AbstractBIT<T,m_T,e_T,i_T,N>& AbstractBIT<T,m_T,e_T,i_T,N>::operator+=( const T ( & a )[N] ) { for( int i = 0 ; i < N ; i++ ){ Add( i , a[i] ); } return *this; }

template <TEMPLETE_ARGUMENTS_FOR_BIT>
void AbstractBIT<T,m_T,e_T,i_T,N>::Add( const int& i , const T& n )
{
  
  int j = i + 1;

  while( j <= N ){

    T& m_fenwick_j = m_fenwick[j];
    m_fenwick_j = m_T( m_fenwick_j , n );
    j += ( j & -j );

  }

  return;
  
}

template <TEMPLETE_ARGUMENTS_FOR_BIT> 
T AbstractBIT<T,m_T,e_T,i_T,N>::InitialSegmentSum( const int& i_final )
{

  T sum = g_e;
  int j = ( i_final < N ? i_final : N - 1 ) + 1;

  while( j > 0 ){

    sum = m_T( sum , m_fenwick[j] );
    j -= j & -j;
    
  }

  return sum;
  
}

template <TEMPLETE_ARGUMENTS_FOR_BIT> inline T AbstractBIT<T,m_T,e_T,i_T,N>::IntervalSum( const int& i_start , const int& i_final ) { return m_T( i_T( InitialSegmentSum( i_start - 1 ) ) , InitialSegmentSum( i_final ) ); }

int MAIN()
{
  UNTIE;
  CEXPR( int , bound_NQ , 100000 );
  CIN_ASSERT( N , 1 , bound_NQ );
  CEXPR( int , bound_B , 1000000000 );
  CIN_ASSERT( B , 1 , bound_B );
  MG::g_B = B;
  MG::g_euler_minus = EulerFunction( B , MG::g_prime , MG::g_exponent ) - 1;
  MG::g_size = MG::g_prime.size();
  MG::g_e.m_n = 1;
  MG::g_e.m_factor = vector<int>( MG::g_size );
  CIN_ASSERT( Q , 1 , bound_NQ );
  CEXPR( ll , bound_Am , 1000000000000000000 );
  static MG A_prep[bound_NQ] = {};
  FOR( i , 0 , N ){
    CIN_ASSERT( Ai , 0 , bound_Am );
    A_prep[i] = MG( move( Ai ) );
  }
  AbstractBIT<MG,op,e,inv,bound_NQ> A{ A_prep };
  N--;
  MG B_inv = MG( B );
  FOR( i , 0 , MG::g_size ){
    B_inv.m_factor[i] *= -1;
  }
  REPEAT( Q ){
    CIN_ASSERT( j , 0 , N );
    CIN_ASSERT( m , 0 , bound_Am );
    CIN_ASSERT( l , 0 , N );
    CIN_ASSERT( r , l , N );
    MG A_j = A.IntervalSum( j , j );
    if( A_j.m_zero == 0 ){
      if( m == 0 ){
	A.Set( j , MG( move( m ) ) );
      } else {
	bool divisible = m == MG::g_B ;
	if( divisible ){
	  FOR( i , 0 , MG::g_size ){
	    if( A_j.m_factor[i] < MG::g_exponent[i] ){
	      divisible = false;
	      break;
	    }
	  }
	}
	if( divisible ){
	  A.Add( j , B_inv );	  
	} else {
	  A.Add( j , MG( move( m ) ) );
	}
      }
    }
    MG A_lr = A.IntervalSum( l , r );
    if( A_lr.m_zero > 0 ){
      COUT( 0 );
    } else {
      ll answer = A_lr.m_n;
      FOR( i , 0 , MG::g_size ){
	ll power = MG::g_prime[i];
	int factor_i = A_lr.m_factor[i];
	while( factor_i != 0 ){
	  if( ( factor_i & 1 ) == 1 ){
	    ( answer *= power ) %= MG::g_B;
	  }
	  ( power *= power ) %= MG::g_B;
	  factor_i >>= 1;
	}
      }
      COUT( answer );
    }
  }
  QUIT;
}

yukicoder

結果

テストケース

ソースコード