結果
| 問題 |
No.2159 Filling 4x4 array
|
| コンテスト | |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2024-04-23 14:44:38 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 675 ms / 5,000 ms |
| コード長 | 11,701 bytes |
| コンパイル時間 | 2,604 ms |
| コンパイル使用メモリ | 217,644 KB |
| 最終ジャッジ日時 | 2025-02-21 08:43:41 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 45 |
ソースコード
#pragma GCC optimize ( "O3" )
//#pragma GCC target ( "avx" )
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
#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 GETLINE( A ) string A; getline( cin , A )
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR )
#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 FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ )
#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
#define DOUBLE( PRECISION , ANSWER ) cout << fixed << setprecision( PRECISION ) << ( ANSWER ) << "\n"; QUIT
#define POWER( ANSWER , ARGUMENT , EXPONENT ) \
TYPE_OF( ARGUMENT ) ANSWER{ 1 }; \
{ \
TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT ); \
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 *= ARGUMENT_FOR_SQUARE_FOR_POWER; \
} \
ARGUMENT_FOR_SQUARE_FOR_POWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \
EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \
} \
} \
#define POWER_MOD( ANSWER , ARGUMENT , EXPONENT , MODULO ) \
TYPE_OF( ARGUMENT ) ANSWER{ 1 }; \
{ \
TYPE_OF( ARGUMENT ) 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; \
} \
} \
#define FACTORIAL_MOD( ANSWER , ANSWER_INV , MAX_I , LENGTH , MODULO ) \
ll ANSWER[LENGTH]; \
ll ANSWER_INV[LENGTH]; \
{ \
ll VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \
ANSWER[0] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL; \
FOREQ( i , 1 , MAX_I ){ \
ANSWER[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= i ) %= MODULO; \
} \
POWER_MOD( FACTORIAL_MAX_INV , ANSWER[MAX_I] , MODULO - 2 , MODULO ); \
ANSWER_INV[MAX_I] = FACTORIAL_MAX_INV; \
FOREQINV( i , MAX_I - 1 , 0 ){ \
ANSWER_INV[i] = ( FACTORIAL_MAX_INV *= i + 1 ) %= MODULO; \
} \
} \
\
// 通常の二分探索
#define BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
ll ANSWER = MAXIMUM; \
{ \
ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \
ll VARIABLE_FOR_BINARY_SEARCH_U = ANSWER; \
ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \
} else { \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
} \
while( VARIABLE_FOR_BINARY_SEARCH_L != ANSWER ){ \
VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \
break; \
} else { \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \
} else { \
VARIABLE_FOR_BINARY_SEARCH_U = ANSWER; \
} \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
} \
} \
} \
\
// 二進法の二分探索
#define BS2( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
ll ANSWER = MINIMUM; \
{ \
ll VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 = 1; \
ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( MAXIMUM ) - ANSWER; \
while( VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 <= VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ){ \
VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 *= 2; \
} \
VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 /= 2; \
ll VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER; \
while( VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 != 0 ){ \
ANSWER = VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 + VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2; \
VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \
VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER; \
break; \
} else if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){ \
VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER; \
} \
VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 /= 2; \
} \
ANSWER = VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2; \
} \
\
template <typename T> inline T Absolute( const T& a ){ return a > 0 ? a : - a; }
template <typename T> inline T Residue( const T& a , const T& p ){ return a >= 0 ? a % p : p - ( - a - 1 ) % p - 1; }
int main()
{
UNTIE;
CEXPR( int , bound , 1000000000 );
int hw[2][4];
int sum[2] = {};
FOR( k , 0 , 2 ){
int ( &hw_k )[4] = hw[k];
int& sum_k = sum[k];
FOR( i , 0 , 4 ){
CIN_ASSERT( hwi , 4 , bound );
sum_k += hw_k[i] = hwi - 4;
}
}
if( sum[0] != sum[1] ){
RETURN( 0 );
}
// 次の繰り上がり計算に使う3以下のデータ6個を2進法で12桁のデータに纏めたもの（以下「桁和」）の上限値
CEXPR( int , assign_sum_lim , 1 << 12 );
// 桁和から元のデータを復元する
static int assign_sum[assign_sum_lim][2][3] = {};
int t_copy;
FOR( t , 0 , assign_sum_lim ){
t_copy = t;
int ( &assign_sum_t )[2][3] = assign_sum[t];
FOR( k , 0 , 2 ){
int ( &assign_sum_t_k )[3] = assign_sum_t[k];
FOR( i , 0 , 3 ){
assign_sum_t_k[i] = t_copy % 4;
t_copy /= 4;
}
}
}
// 次の桁を表す1以下のデータ9個を2進法で9桁のデータに纏めてたもの（以下「桁値」）の上限
CEXPR( int , assign_lim , 1 << 9 );
// 桁値を動かした時の次の桁和の重複を格納
static int multiple[assign_sum_lim] = {};
int assign[3][3] = {};
int assign_sum_curr;
FOR( t , 0 , assign_lim ){
t_copy = t;
FOR( i , 0 , 3 ){
int ( &assign_i )[3] = assign[i];
FOR( j , 0 , 3 ){
assign_i[j] = t_copy % 2;
t_copy /= 2;
}
}
assign_sum_curr = 0;
{
FOR( i , 0 , 3 ){
assign_sum_curr *= 4;
int ( &assign_i )[3] = assign[i];
FOR( j , 0 , 3 ){
assign_sum_curr += assign_i[j];
}
}
}
{
FOR( j , 0 , 3 ){
assign_sum_curr *= 4;
FOR( i , 0 , 3 ){
assign_sum_curr += assign[i][j];
}
}
}
multiple[assign_sum_curr]++;
}
// multipleが正の桁和の抽出
int valid_sum_num = 0;
static int valid_sum[assign_lim];
FOR( t , 0 , assign_sum_lim ){
if( multiple[t] > 0 ){
valid_sum[valid_sum_num] = t;
valid_sum_num++;
}
}
// hwの成分を2進法表記した時の特定の桁のデータ
int hw_r[2][4];
// 繰り上がりの値である(4-1)以下のデータ8個を2進法で16桁のデータ（以下「状態」）に纏めたものの上限値
CEXPR( int , state_lim , 1 << 16 );
// 状態から元のデータを復元する
static int state[state_lim][2][4] = {};
FOR( s , 0 , state_lim ){
int ( &state_s )[2][4] = state[s];
t_copy = s;
FOR( k , 0 , 2 ){
int ( &state_s_k )[4] = state_s[k];
FOR( i , 0 , 4 ){
state_s_k[i] = t_copy % 4;
t_copy /= 4;
}
}
}
// 次の状態を格納
int hw_next[2][4];
// 各状態ごとの、特定の桁までの数え上げ
vector<ll> count[2] = {};
vector<ll> count_init( state_lim );
{
vector<ll>& count0 = count[0];
count0 = count_init;
count0[0] = 1;
}
int i_prev = 0;
int i_curr = 1;
int valid_sum_t , rest_assign_sum , diff , sa_sum , s_next;
CEXPR( ll , P , 998244353 );
bool computing = true;
while( computing ){
vector<ll>& count_prev = count[i_prev];
vector<ll>& count_curr = count[i_curr];
count_curr = count_init;
FOR( k , 0 , 2 ){
int ( &hw_k )[4] = hw[k];
int ( &hw_r_k )[4] = hw_r[k];
FOR( i , 0 , 4 ){
hw_r_k[i] = hw_k[i] % 2;
}
}
FOR( s , 0 , state_lim ){
ll& count_prev_s = count_prev[s];
if( count_prev_s != 0 ){
int ( &state_s )[2][4] = state[s];
FOR( t , 0 , valid_sum_num ){
valid_sum_t = valid_sum[t];
int ( &assign_sum_t )[2][3] = assign_sum[valid_sum_t];
// 桁和から次の状態を計算する（つまり残りの16-9個の変数を決定し和を8個取る）
{
int k = 0;
int ( &hw_r_k )[4] = hw_r[k];
int ( &hw_next_k )[4] = hw_next[k];
int ( &assign_sum_t_k )[3] = assign_sum_t[k];
int ( &state_s_k )[4] = state_s[k];
rest_assign_sum = 0;
FOR( i , 0 , 3 ){
int& hw_next_k_i = hw_next_k[i];
sa_sum = state_s_k[i] + assign_sum_t_k[i];
rest_assign_sum += diff = ( hw_r_k[i] + sa_sum ) % 2;
hw_next_k_i = ( sa_sum + diff ) / 2;
}
}
{
int k = 1;
int ( &hw_r_k )[4] = hw_r[k];
int ( &hw_next_k )[4] = hw_next[k];
int ( &assign_sum_t_k )[3] = assign_sum_t[k];
int ( &state_s_k )[4] = state_s[k];
{
int i = 3;
int& hw_next_k_i = hw_next_k[i];
sa_sum = state_s_k[i] + rest_assign_sum;
diff = ( hw_r_k[i] + sa_sum ) % 2;
hw_next_k_i = ( sa_sum + diff ) / 2;
}
rest_assign_sum = 0;
FOR( i , 0 , 3 ){
int& hw_next_k_i = hw_next_k[i];
sa_sum = state_s_k[i] + assign_sum_t_k[i];
rest_assign_sum += diff = ( hw_r_k[i] + sa_sum ) % 2;
hw_next_k_i = ( sa_sum + diff ) / 2;
}
}
{
int k = 0;
int ( &hw_r_k )[4] = hw_r[k];
int ( &hw_next_k )[4] = hw_next[k];
int ( &state_s_k )[4] = state_s[k];
{
int i = 3;
int& hw_next_k_i = hw_next_k[i];
sa_sum = state_s_k[i] + rest_assign_sum;
diff = ( hw_r_k[i] + sa_sum ) % 2;
hw_next_k_i = ( sa_sum + diff ) / 2;
}
}
s_next = 0;
FOREQINV( k , 1 , 0 ){
int ( &hw_next_k )[4] = hw_next[k];
FOREQINV( i , 3 , 0 ){
s_next = s_next * 4 + hw_next_k[i];
}
}
count_curr[s_next] += count_prev_s * multiple[valid_sum_t];
}
}
}
FOR( s , 0 , state_lim ){
count_curr[s] %= P;
}
computing = false;
FOR( k , 0 , 2 ){
int ( &hw_k )[4] = hw[k];
FOR( i , 0 , 4 ){
if( ( hw_k[i] /= 2 ) != 0 ){
computing = true;
}
}
}
swap( i_prev , i_curr );
}
// 最終的には繰り上がりがなくなっていないと一致しないので、状態は0のみ
RETURN( count[i_prev][0] );
}