#853522 (C++17(gcc12)) No.3492 区間冪乗加算一点取得

提出ソース

結果

問題	No.3492 区間冪乗加算一点取得
コンテスト
ユーザー	👑 p-adic
提出日時	2023-03-28 08:52:24
言語	C++17(gcc12) (gcc 12.4.0 + boost 1.89.0) コンパイル: `g++-12 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_` 実行: `./a.out`
結果	AC
実行時間	152 ms / 4,000 ms
コード長	7,311 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	1,526 ms
コンパイル使用メモリ	88,776 KB
実行使用メモリ	19,584 KB
最終ジャッジ日時	2026-04-03 20:50:28
合計ジャッジ時間	3,125 ms
ジャッジサーバーID （参考情報）	judge3_0 / judge1_0

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

ファイルパターン	結果
other	AC * 27

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

ソースコード

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 <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 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 REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES )
#define QUIT return 0
#define COUT( ANSWER ) cout << ( ANSWER ) << "\n"

struct ModB
{
  ll m_n;
  static ll g_B;
  inline ModB() : m_n() {};
  inline ModB( const ll& n ) : m_n( n % g_B ) {};
  inline ModB( const ModB& n ) : m_n( n.m_n ) {};
  inline ModB( ModB&& n ) : m_n( move( n.m_n ) ) {};
  inline ModB& operator=( const ModB& n ) { m_n = n.m_n; return *this; }
  inline ModB& operator=( ModB&& n ) { m_n = move( n.m_n ); return *this; }
  inline ModB& operator+=( const ModB& n ) { ( m_n += n.m_n ) < g_B ? m_n : m_n -= g_B; return *this; }
  inline ModB& operator*=( const ll& n ) { ( m_n *= n ) %= g_B; return *this; }
};

ll ModB::g_B = 1;
inline ModB operator+( const ModB& n0 , const ModB& n1 ) { ll n = n0.m_n + n1.m_n; return ModB( n < ModB::g_B ? n : n -= ModB::g_B ); }
inline ModB operator-( const ModB& n ) { return ModB( n.m_n == 0 ? 0 : ModB::g_B - n.m_n ); }
inline ModB operator-( const ModB& n0 , const ModB& n1 ) { ll n = n0.m_n - n1.m_n; return ModB( n < 0 ? n += ModB::g_B : n ); }
inline ModB operator*( const ModB& n0 , const ModB& n1 ) { return ModB( n0.m_n * n1.m_n ); }

template <typename T , int N>
class BIT
{
private:
  T m_fenwick[N + 1];

public:
  inline BIT();
  BIT( const T ( & a )[N] );

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

  inline BIT<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 <typename T , int N> inline BIT<T,N>::BIT() : m_fenwick() {}
template <typename T , int N>
BIT<T,N>::BIT( 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_fenwick[i];
      i -= ( i & -i );

    }

  }

}

template <typename T , int N> inline void BIT<T,N>::Set( const int& i , const T& n ) { Add( i , n - IntervalSum( i , i ) ); }

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

template <typename T , int N>
void BIT<T,N>::Add( const int& i , const T& n )
{
  
  int j = i + 1;

  while( j <= N ){

    m_fenwick[j] += n;
    j += ( j & -j );

  }

  return;
  
}

template <typename T , int N> 
T BIT<T,N>::InitialSegmentSum( const int& i_final )
{

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

  while( j > 0 ){

    sum += m_fenwick[j];
    j -= j & -j;
    
  }

  return sum;
  
}

template <typename T , int N> inline T BIT<T,N>::IntervalSum( const int& i_start , const int& i_final ) { return InitialSegmentSum( i_final ) - InitialSegmentSum( i_start - 1 ); }

template <typename T , int N>
class IntervalAddBIT
{
private:
  // 母関数の微分の負の階差数列（(i-1)a_{i-1} - ia_i）の管理
  BIT<T,N> m_bit_0;
  // 階差数列（a_i - a_{i-1}）の管理
  BIT<T,N> m_bit_1;

public:
  inline IntervalAddBIT();
  inline IntervalAddBIT( const T ( & a )[N] );

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

  inline IntervalAddBIT<T,N>& operator+=( const T ( & a )[N] );
  inline void Add( const int& i , const T& n );
  inline void IntervalAdd( const int& i_start , const int& i_final , const T& n );

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

template <typename T , int N> inline IntervalAddBIT<T,N>::IntervalAddBIT() : m_bit_0() , m_bit_1() {}
template <typename T , int N> inline IntervalAddBIT<T,N>::IntervalAddBIT( const T ( & a )[N] ) : m_bit_0() , m_bit_1() { operator+=( a ); }

template <typename T , int N> inline void IntervalAddBIT<T,N>::Set( const int& i , const T& n ) { Add( i , n - IntervalSum( i , i ) ); }

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

template <typename T , int N> inline void IntervalAddBIT<T,N>::Add( const int& i , const T& n ) { IntervalAdd( i , i , n ); }

template <typename T , int N> inline void IntervalAddBIT<T,N>::IntervalAdd( const int& i_start , const int& i_final , const T& n ) { m_bit_0.Add( i_start , - ( i_start - 1 ) * n ); m_bit_0.Add( i_final + 1 , i_final * n ); m_bit_1.Add( i_start , n ); m_bit_1.Add( i_final + 1 , - n ); }


template <typename T , int N> inline T IntervalAddBIT<T,N>::InitialSegmentSum( const int& i_final ) { return m_bit_0.InitialSegmentSum( i_final ) + i_final * m_bit_1.InitialSegmentSum( i_final ); }

template <typename T , int N> inline T IntervalAddBIT<T,N>::IntervalSum( const int& i_start , const int& i_final ) { return InitialSegmentSum( i_final ) - InitialSegmentSum( i_start - 1 ); }

int MAIN()
{
  UNTIE;
  CEXPR( int , bound_N , 10000 );
  CIN_ASSERT( N , 1 , bound_N );
  CEXPR( ll , bound_B , 1000000000 );
  CIN_ASSERT( B , 1 , bound_B );
  ModB::g_B = move( B );
  CEXPR( int , bound_Q , 10000 );
  CIN_ASSERT( Q , 1 , bound_Q );
  CEXPR( ll , bound_C , 1000000000000000000 );
  CEXPR( int , bound_D , 100 );
  vector<ModB> comb[bound_D + 1] = {};
  ModB one{ 1 };
  comb[0].push_back( one );
  FOREQ( d0 , 1 , bound_D ){
    vector<ModB>& comb_prev = comb[d0 - 1];
    vector<ModB>& comb_curr = comb[d0];
    comb_curr.reserve( d0 + 1 );
    comb_curr[0] = comb_curr[d0] = one;
    FOR( d1 , 1 , d0 ){
      ( comb_curr[d1] = comb_prev[d1 - 1] ) += comb_prev[d1];
    }
  }
  static IntervalAddBIT<ModB,bound_N> A[bound_D + 1] = {};
  REPEAT( Q ){
    CIN_ASSERT( L , 1 , N );
    CIN_ASSERT( M , L , N );
    CIN_ASSERT( R , M , N );
    CIN_ASSERT( C , 0 , bound_C );
    CIN_ASSERT( D , 0 , bound_D );
    ModB power_C{ one };
    vector<ModB>& comb_D = comb[D];
    C %= ModB::g_B;
    FOREQINV( d , D , 0 ){
      A[d].IntervalAdd( L - 1 , R - 1 , comb_D[d] * power_C );
      power_C *= C;
    }
    ModB power_M{ 1 };
    ModB answer{};
    M %= ModB::g_B;
    FOREQ( d , 0 , bound_D ){
      answer += A[d].IntervalSum( M - 1 , M - 1 ) * power_M;
      power_M *= M;
    }
    COUT( answer.m_n );
  }
  QUIT;
}

yukicoder

結果

ソースコード