結果
問題 | No.2651 [Cherry 6th Tune B] $\mathbb{C}$omplex комбинат |
ユーザー | askr58 |
提出日時 | 2024-02-23 22:45:05 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 391 ms / 2,500 ms |
コード長 | 2,117 bytes |
コンパイル時間 | 3,829 ms |
コンパイル使用メモリ | 251,500 KB |
実行使用メモリ | 7,980 KB |
最終ジャッジ日時 | 2024-02-23 22:45:22 |
合計ジャッジ時間 | 16,965 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,676 KB |
testcase_01 | AC | 2 ms
6,676 KB |
testcase_02 | AC | 319 ms
6,676 KB |
testcase_03 | AC | 303 ms
6,676 KB |
testcase_04 | AC | 303 ms
6,676 KB |
testcase_05 | AC | 305 ms
6,676 KB |
testcase_06 | AC | 329 ms
6,676 KB |
testcase_07 | AC | 305 ms
6,676 KB |
testcase_08 | AC | 305 ms
6,676 KB |
testcase_09 | AC | 304 ms
6,676 KB |
testcase_10 | AC | 329 ms
6,676 KB |
testcase_11 | AC | 305 ms
6,676 KB |
testcase_12 | AC | 304 ms
6,676 KB |
testcase_13 | AC | 306 ms
6,676 KB |
testcase_14 | AC | 330 ms
6,676 KB |
testcase_15 | AC | 304 ms
6,676 KB |
testcase_16 | AC | 305 ms
6,676 KB |
testcase_17 | AC | 306 ms
6,676 KB |
testcase_18 | AC | 312 ms
6,676 KB |
testcase_19 | AC | 305 ms
7,524 KB |
testcase_20 | AC | 391 ms
6,676 KB |
testcase_21 | AC | 92 ms
6,676 KB |
testcase_22 | AC | 169 ms
6,676 KB |
testcase_23 | AC | 207 ms
6,676 KB |
testcase_24 | AC | 252 ms
7,172 KB |
testcase_25 | AC | 18 ms
6,676 KB |
testcase_26 | AC | 148 ms
6,676 KB |
testcase_27 | AC | 299 ms
7,912 KB |
testcase_28 | AC | 249 ms
6,784 KB |
testcase_29 | AC | 95 ms
6,676 KB |
testcase_30 | AC | 22 ms
6,676 KB |
testcase_31 | AC | 251 ms
7,152 KB |
testcase_32 | AC | 39 ms
6,676 KB |
testcase_33 | AC | 228 ms
6,804 KB |
testcase_34 | AC | 140 ms
6,676 KB |
testcase_35 | AC | 302 ms
7,516 KB |
testcase_36 | AC | 373 ms
6,676 KB |
testcase_37 | AC | 306 ms
7,980 KB |
testcase_38 | AC | 289 ms
7,980 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; constexpr const int maxa=1000000001; constexpr const ll mod=998244353; ll euclid(ll a,ll b,ll& x,ll& y){ if(b==0){ x=1;y=0; return a; }else{ ll d=euclid(b,a%b,x,y); ll t=x; x=y; y=t-(a/b)*y; return d; } } ll inv(ll p){ ll x,y; euclid(p,mod,x,y); return (x+mod)%mod; } struct c{ ll x,y; c(){x=0;y=0;} c(ll x,ll y):x(x),y(y){} ll abs(){ return (x*x+y*y)%mod; } c conj(){ return c(x,(mod-y)%mod); } void print(){ cout<<to_string(x)+"+("+to_string(y)+")*i"<<endl; } }; c operator+ (c x,c y){ return c((x.x+y.x+2*mod)%mod,(x.y+y.y+2*mod)%mod); } c operator* (c x,c y){ return c(((x.x+mod)%mod*(y.x+mod)%mod-(x.y+mod)%mod*(y.y+mod)%mod+mod)%mod,((x.x+mod)%mod*(y.y+mod)%mod+(x.y+mod)%mod*(y.x+mod)%mod+mod)%mod); } c operator/ (c x,ll y){ return c(((x.x+mod)*inv(y))%mod,((x.y+mod)*inv(y))%mod); } c operator% (c x,ll y){ return c((x.x+mod)%y,(x.y+mod)%y); } int main() { int t; cin>>t; while(t--){ int n; cin>>n; vector<c> z(n); for(int i=0;i<n;i++){ ll x,y; cin>>x>>y; z[i]=c(x,y); } vector<ll> sumsr(2); vector<c> sumsc(2); ll ans=0; for(int i=0;i<n;i++){ ans+=sumsr[0]*inv(z[i].abs())+sumsr[1]*z[i].abs()-(sumsc[0]*(z[i].conj()*z[i].conj()/z[i].abs())+sumsc[1]*(z[i]*z[i]/z[i].abs())).x; //z[i].conj().print(); //(z[i].conj()*z[i].conj()).print(); //(z[i].conj()*z[i].conj()/z[i].abs()).print(); //(sumsc[0]*(z[i].conj()*z[i].conj()/z[i].abs())+sumsc[1]*(z[i]*z[i]/z[i].abs())).print(); sumsr[0]=(sumsr[0]+z[i].abs()+mod)%mod; sumsr[1]=(sumsr[1]+inv(z[i].abs())+mod)%mod; sumsc[0]=(sumsc[0]+z[i]*z[i]/z[i].abs())%mod; sumsc[1]=(sumsc[1]+z[i].conj()*z[i].conj()/z[i].abs())%mod; ans=(ans+mod)%mod; } cout<<ans<<endl; } return 0; }