#907037 (C++17(gcc12)) No.2651 [Cherry 6th Tune B] $\mathbb{C}$omplex комбинат

• 問題: No.2651 [Cherry 6th Tune B] $\mathbb{C}$omplex комбинат
• ユーザー: 👑 p-adic
• 提出日時: 2023-08-23 11:11:16
• 言語: C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 120 ms / 2,500 ms
• コード長: 8,134 bytes
• コンパイル時間: 10,692 ms
• コンパイル使用メモリ: 274,820 KB
• 最終ジャッジ日時: 2025-02-16 12:31:17
• ジャッジサーバーID （参考情報）: judge5 / judge2

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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#ifdef DEBUG
  #define _GLIBCXX_DEBUG
  #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ); signal( SIGABRT , &AlertAbort )
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE )
  #define CERR( MESSAGE ) cerr << MESSAGE << endl;
  #define COUT( ANSWER ) cout << "出力： " << ANSWER << endl
  #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック： " << ( MIN ) << ( ( MIN ) <= A ? "<=" : ">" ) << A << ( A <= ( MAX ) ? "<=" : ">" ) << ( 
      MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) )
#else
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
  #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE )
  #define CERR( MESSAGE ) 
  #define COUT( ANSWER ) cout << ANSWER << "\n"
  #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define TYPE_OF( VAR ) decay_t<decltype( VAR )>
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#define CIN( LL , A ) LL A; cin >> A
#define SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX )
#define CIN_ASSERT( A , MIN , MAX ) TYPE_OF( MAX ) A; SET_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 REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT_ ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES )
#define QUIT return 0
#ifdef DEBUG
  inline void AlertAbort( int n ) { CERR( 
      "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); }
#endif
template <typename T> inline T Residue( const T& a , const T& p ){ return a >= 0 ? a % p : p - 1 - ( ( - ( a + 1 ) ) % p ); }
#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;               \
    }                                   \
  }                                 \
// 入力フォーマットチェック用
// 1行中の変数の個数をSEPARATOR区切りで確認
#define GETLINE_COUNT( S , VARIABLE_NUMBER , SEPARATOR ) GETLINE( S ); int VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S = 0; int 
    VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S  = S.size(); { int size = S.size(); int count = 0; for( int i = 0 ; i < size ; i++ ){ if( S.substr( i , 1 
    ) == SEPARATOR ){ count++; } } assert( count + 1 == VARIABLE_NUMBER ); }
// 余計な入力の有無を確認
#ifdef DEBUG
  #define CHECK_REDUNDANT_INPUT 
#else
  #define CHECK_REDUNDANT_INPUT string VARIABLE_FOR_CHECK_REDUNDANT_INPUT = ""; cin >> VARIABLE_FOR_CHECK_REDUNDANT_INPUT; assert( 
      VARIABLE_FOR_CHECK_REDUNDANT_INPUT == "" ); assert( ! cin )
  // #define CHECK_REDUNDANT_INPUT string VARIABLE_FOR_CHECK_REDUNDANT_INPUT = ""; getline( cin , VARIABLE_FOR_CHECK_REDUNDANT_INPUT ); assert( 
      VARIABLE_FOR_CHECK_REDUNDANT_INPUT == "" ); assert( ! cin )
#endif
// |N| <= BOUNDを満たすNをSから構築
#define STOI( S , N , BOUND ) TYPE_OF( BOUND ) N = 0; { bool VARIABLE_FOR_POSITIVITY_FOR_GETLINE = true; assert( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ 
    ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ); if( S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) == "-" ){ 
    VARIABLE_FOR_POSITIVITY_FOR_GETLINE = false; VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; assert( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < 
    VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ); } assert( S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) != " " ); string 
    VARIABLE_FOR_LETTER_FOR_GETLINE{}; int VARIABLE_FOR_DIGIT_FOR_GETLINE{}; while( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < 
    VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ? ( VARIABLE_FOR_LETTER_FOR_GETLINE = S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) ) != " " : 
    false ){ VARIABLE_FOR_DIGIT_FOR_GETLINE = stoi( VARIABLE_FOR_LETTER_FOR_GETLINE ); assert( N < BOUND / 10 ? true : N == BOUND / 10 && 
    VARIABLE_FOR_DIGIT_FOR_GETLINE <= BOUND % 10 ); N = N * 10 + VARIABLE_FOR_DIGIT_FOR_GETLINE; VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } if( ! 
    VARIABLE_FOR_POSITIVITY_FOR_GETLINE ){ N *= -1; } if( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ){ 
    VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } }
// SをSEPARATORで区切りTを構築
#define SEPARATE( S , T , SEPARATOR ) string T{}; { assert( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ); int 
    VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S_prev = VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S; assert( S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ 
    ## S , 1 ) != SEPARATOR ); string VARIABLE_FOR_LETTER_FOR_GETLINE{}; while( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < 
    VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ? ( VARIABLE_FOR_LETTER_FOR_GETLINE = S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) ) != 
    SEPARATOR : false ){ VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } T = S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S_prev , 
    VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S - VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S_prev ); if( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < 
    VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ){ VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } }
int main()
{
  UNTIE;
  DEXPR( int , bound_T , 100000 , 100 );
  CIN_ASSERT( T , 1 , bound_T );
  CEXPR( int , bound_N_sum , 300000 );
  CEXPR( int , bound_xy , 20000 );
  CEXPR( ll , P , 998244353 );
  int N_sum = 0;
  REPEAT( T ){
    // |Z/z_j - zj/Z|^2
    // = |(Z^2 - zj^2)/(zj Z)|^2
    // = |Z - zj|^2 |Z + zj|^2/(|zj|^2 |Z|^2)
    // = ((X - xj)^2 + (Y - yj)^2)((X + xj)^2 + (Y + yj)^2)
    //   /((xj^2 + yj^2)(X^2 + Y^2))
    // = (X^2 - 2xj X + Y^2 - 2yj Y + xj^2 + yj^2)
    //   (X^2 + 2xj X + Y^2 + 2yj Y + xj^2 + yj^2)
    //   /((xj^2 + yj^2)(X^2 + Y^2))
    // = ((X^2 + Y^2 + xj^2 + yj^2)^2 - (2xj X + 2yj Y)^2)
    //   /((xj^2 + yj^2)(X^2 + Y^2))
    // = (
    //     (X^2 + Y^2)^2 + 2(xj^2 + yj^2)(X^2 + Y^2) + (xj^2 + yj^2)^2
    //     - 4xj^2 X^2 - 8xj yj X Y + 4yj^2 Y^2
    //   )
    //   /((xj^2 + yj^2)(X^2 + Y^2))
    
    // = (1/(xj^2 + yj^2)) * (X^2 + Y^2)
    //   +2
    //   +(xj^2 + yj^2) * 1/(X^2 + Y^2)
    //   -(4xj^2/(xj^2 + yj^2)) * X^2/(X^2 + Y^2)
    //   -(8xjyj/(xj^2 + yj^2)) * XY/(X^2 + Y^2)
    //   -(4yj^2/(xj^2 + yj^2)) * Y^2/(X^2 + Y^2)
    ll sum0 = 0;
    ll sum1 = 0;
    ll sum2 = 0;
    ll sum3 = 0;
    ll sum4 = 0;
    ll sum5 = 0;
    ll answer = 0;
    CIN_ASSERT( N , 2 , bound_N_sum );
    N_sum += N;
    FOR( i , 0 , N ){
      CIN_ASSERT( x , -bound_xy , bound_xy );
      CIN_ASSERT( y , -bound_xy , bound_xy );
      int x2 = x * x;
      int xy = x * y;
      int y2 = y * y;
      int x2y2 = x2 + y2;
      assert( x2y2 != 0 );
      POWER_MOD( x2y2inv , x2y2 , P - 2 , P );
      answer +=
    sum0 * x2y2 % P
    + sum1
    + sum2 * x2y2inv % P
    - sum3 * x2 % P * x2y2inv % P
    - sum4 * xy % P * x2y2inv % P
    - sum5 * y2 % P * x2y2inv % P;
      ( sum0 += x2y2inv ) < P ? sum0 : sum0 -= P;
      ( sum1 += 2 );
      ( sum2 += x2y2 ) < P ? sum2 : sum2 -= P;
      ( sum3 += 4 * ( x2 * x2y2inv ) ) %= P;
      ( sum4 += 8 * ( xy * x2y2inv ) ) %= P;
      ( sum5 += 4 * ( y2 * x2y2inv ) ) %= P;
    }
    COUT( Residue( answer , P ) );
  }
  CHECK_REDUNDANT_INPUT;
  assert( N_sum <= bound_N_sum );
  cerr << "入力の強さ確認： " << T << "," << N_sum << "\n";
  QUIT;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX