#pragma GCC optimize ( "O3" ) #pragma GCC optimize( "unroll-loops" ) #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) #include using namespace std; using ll = long long; #define ATT __attribute__( ( target( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) ) ) #define TYPE_OF( VAR ) remove_const::type >::type #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define CEXPR( LL , BOUND , VALUE ) constexpr 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 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 inline T Absolute( const T& a ){ return a > 0 ? a : -a; } inline CEXPR( int , bound_N , 13 ); inline CEXPR( int , bound_x_shift , bound_N * ( bound_N + 1 ) ); inline CEXPR( int , bound_x , bound_x_shift >> 1 ); inline CEXPR( int , bound_B , 1 << bound_N ); // O(N 3^N) // inline CEXPR( int , three_bound_N , 1594323 ); // 3^13 // struct X // { // bool m_val[bound_B][bound_N+1][bound_x_shift+1]; // constexpr X() : m_val() // { // int S_copy = 0; // int B = 0; // int p = 0; // int x_shift = 0; // int c = 0; // FOR( S , 1 , three_bound_N ){ // S_copy = S; // B = p = 0; // x_shift = bound_x; // FOR( d , 0 , bound_N ){ // c = S_copy % 3; // if( c != 0 ){ // B += 1 << d; // c == 1 ? x_shift -= d : ( p++ , x_shift += d ); // } // S_copy /= 3; // } // m_val[B][p][x_shift] = true; // } // } // }; // O(N^3 2^N) struct X { bool m_val[bound_B][bound_N+1][bound_x_shift+1]; constexpr X() : m_val() { FOR( B , 1 , bound_B ){ bool ( &xB )[bound_N+1][bound_x_shift+1] = m_val[B]; int B_copy = B; int A[bound_N] = {}; int B_card = 0; FOR( d , 0 , bound_N ){ if( ( B_copy & 1 ) == 1 ){ A[B_card++] = d; } B_copy >>= 1; } int power = 1 << B_card; FOREQ( B_p , 0 , power ){ B_copy = B_p; int x_shift = bound_x; int p = 0; FOR( d , 0 , B_card ){ ( B_copy & 1 ) == 1 ? ( p++ , x_shift += A[d] ) : x_shift -= A[d]; B_copy >>= 1; } xB[p][x_shift] = true; } } } }; struct CombSum { int m_val[bound_N+1]; constexpr CombSum() : m_val() { FOREQ( N , 1 , bound_N ){ if( ( N & 1 ) == 1 ){ m_val[N] = 1 << ( N - 1 ); } else { int& m_val_N = m_val[N]; int comb = 1; FOREQ( p , 1 , N ){ ( comb *= ( N - p + 1 ) ) /= p; if( ( p & 1 ) == 1 ){ m_val_N += comb; } } } } } }; int main() { UNTIE; CEXPR( int , bound_T , 6000 ); CIN_ASSERT( T , 1 , bound_T ); CEXPR( int , bound_Pl , 100000000 ); CEXPR( int , bound_Pr , 1000000000 ); CEXPR( ll , bound_Ai , 1000000000 ); CEXPR( ll , bound_evenness , ll( 1 ) << 62 ); // constexpr X x{}; // 33554432θΆ…γˆγ‚‹ static X x{}; constexpr CombSum comb_sum{}; REPEAT( T ){ CIN_ASSERT( N , 1 , bound_N ); CIN_ASSERT( P , bound_Pl , bound_Pr ); CIN_ASSERT( A0 , 1 , bound_Ai ); CIN_ASSERT( A1 , A0 , bound_Ai ); ll d = A1 - A0; FOR( i , 2 , N ){ cin >> A1; } ll answer; if( d == 0 ){ answer = comb_sum.m_val[N] * A0; } else { answer = 0; if( d < 0 ){ d *= -1; A0 -= d * ( N - 1 ); } int power_N = 1 << N; FOR( B , 1 , power_N ){ const bool ( &xB )[bound_N+1][bound_x_shift+1] = x.m_val[B]; int B_copy = B; int B_card = 0; while( B_copy != 0 ){ if( ( B_copy & 1 ) == 1 ){ B_card++; } B_copy >>= 1; } ll evenness = bound_evenness; FOREQ( p , 0 , B_card ){ const bool ( &xBp )[bound_x_shift+1] = xB[p]; ll l = ( ( B_card - ( p << 1 ) ) * A0 ) / d; if( l > bound_N ){ l = bound_N; } ll r = l + 1; if( r < -bound_N ){ r = -bound_N; } ll A0_factor = ( ( p << 1 ) - B_card ) * A0; bool searching = l >= -bound_N; while( searching ){ if( xBp[l+bound_x] ){ searching = false; ll evenness_curr = Absolute( A0_factor + l * d ); if( evenness > evenness_curr ){ evenness = evenness_curr; } } else { if( --l < -bound_x ){ searching = false; } } } searching = r <= bound_N; while( searching ){ if( xBp[r+bound_x] ){ searching = false; ll evenness_curr = Absolute( A0_factor + r * d ); if( evenness > evenness_curr ){ evenness = evenness_curr; } } else { if( ++r > bound_x ){ searching = false; } } } } answer += evenness; } } COUT( answer % P ); } QUIT; }