結果
問題 | No.2274 三角彩色 |
ユーザー |
👑 |
提出日時 | 2023-02-19 09:01:13 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 32 ms / 2,000 ms |
コード長 | 3,649 bytes |
コンパイル時間 | 11,628 ms |
コンパイル使用メモリ | 289,048 KB |
最終ジャッジ日時 | 2025-02-10 19:03:52 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#pragma GCC optimize ( "O3" )#pragma GCC optimize( "unroll-loops" )#pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )#include <bits/stdc++.h>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 ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES )#define QUIT return 0#define COUT( ANSWER ) cout << ( ANSWER ) << "\n";#define RETURN( ANSWER ) COUT( ANSWER ); QUIT#define POWER_MOD( ANSWER , ARGUMENT , EXPONENT , MODULO ) \ll ANSWER{ 1 }; \{ \ll ARGUMENT_FOR_SQUARE_FOR_POWER = ( MODULO + ( ( ARGUMENT ) % MODULO ) ) % MODULO; \TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \} \ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \} \} \template <typename T> inline T Residue( const T& a , const T& p ){ return a >= 0 ? a % p : p - 1 - ( ( - ( a + 1 ) ) % p ); }template <int bound_L , int bound_M>int Rank( bitset<bound_M> ( &A )[bound_L] , const int& L , const int& M ){int i_min = 0;int i_curr;int j_curr = 0;while( i_min < L && j_curr < M ){i_curr = i_min;while( A[i_curr][j_curr] == 0 && i_curr < L ){i_curr++;}if( i_curr < L ){swap( A[i_min] , A[i_curr] );const bitset<bound_M>& A_i_min = A[i_min];i_min++;while( ++i_curr < L ){bitset<bound_M>& A_i_curr = A[i_curr];if( A_i_curr[j_curr] == 1 ){A_i_curr ^= A_i_min;}}}j_curr++;}return i_min;}int MAIN(){UNTIE;CEXPR( ll , bound_N , 1000000000000000000 );CIN_ASSERT( N , 3 , bound_N );N--;CEXPR( int , bound_M , 400 );CIN_ASSERT( M , 3 , bound_M );CEXPR( ll , bound_B , 1000000000 );CIN_ASSERT( B , 2 , bound_B );CEXPR( int , bound_Q , 1000 );CIN_ASSERT( Q , 1 , bound_Q );CEXPR( int , bound_V , bound_M * 2 );int V = 0;map<ll,int> vertex{};bitset<bound_V> d1[bound_M] = {};FOR( m , 0 , M ){bitset<bound_V>& d1m = d1[m];CIN_ASSERT( i , 0 , N );d1m[ vertex.count( i ) == 0 ? vertex[i] = V++ : vertex[i] ] = 1;CIN_ASSERT( j , i + 1 , N );d1m[ vertex.count( j ) == 0 ? vertex[j] = V++ : vertex[j] ] = 1;}int M_minus = M - 1;bitset<bound_M> d2[bound_Q] = {};FOR( q , 0 , Q ){bitset<bound_M>& d2q = d2[q];CIN_ASSERT( m0 , 0 , M_minus );d2q[m0] = 1;CIN_ASSERT( m1 , m0 + 1 , M_minus );d2q[m1] = 1;CIN_ASSERT( m2 , m1 + 1 , M_minus );d2q[m2] = 1;assert( ( d1[m0] ^ d1[m1] ^ d1[m2] ) == 0 );}int rank1 = Rank<bound_M,bound_V>( d1 , M , V );int rank2 = Rank<bound_Q,bound_M>( d2 , Q , M );POWER_MOD( ker1 , 2 , M - rank1 , B );POWER_MOD( im2 , 2 , rank2 , B );cout << Residue<ll>( ker1 - im2 , B ) << " " << im2 << "\n";QUIT;}