結果
問題 | No.1548 [Cherry 2nd Tune B] 貴方と私とサイクルとモーメント |
ユーザー |
👑 ![]() |
提出日時 | 2021-04-30 22:57:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,454 bytes |
コンパイル時間 | 1,236 ms |
コンパイル使用メモリ | 76,984 KB |
実行使用メモリ | 37,328 KB |
最終ジャッジ日時 | 2024-12-14 21:30:27 |
合計ジャッジ時間 | 147,695 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 TLE * 19 |
ソースコード
#pragma GCC optimize("Ofast") #include<iostream> #include<vector> using namespace std; using ll=long long; ll mod=998244353; ll sub(ll a, ll b) {return ((a-b)%mod+mod)%mod;} ll mul(ll a, ll b) {return (a*b)%mod;} ll mul(ll a, ll b, ll c) { return mul(a,mul(b,c));} ll pow_mod(ll a, ll n){ ll x=1; while (n){ n--; x*=a; x%=mod; } return x; } ll second(ll s1, ll s2, ll l_inv){ return sub(s2,mul(mul(s1,s1),l_inv)); } ll third(ll s1, ll s2, ll s3, ll l_inv){ ll X=sub(s3,3*mul(s2,s1,l_inv)); X+=2*mul(pow_mod(s1,3),l_inv,l_inv); return X%mod; } ll forth(ll s1, ll s2, ll s3, ll s4, ll l_inv){ ll X=sub(s4,4*mul(s3,s1,l_inv)); X+=6*mul(s2,pow_mod(s1,2),pow_mod(l_inv,2)); X-=3*mul(pow_mod(s1,4),pow_mod(l_inv,3)); X%=mod; if (X<0) X+=mod; return X; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ll N; cin >> N; ll a; vector<vector<ll>> A(N+1,vector<ll> (5,1)); for (int i=1; i<=N; i++){ cin >> a; for (int j=1; j<=4; j++){ A[i][j]=(A[i][j-1]*a)%mod; } } vector<ll> L_inv(N+1,0); L_inv[1]=1; int q,r; for (int i=2;i<=N;i++){ q=mod/i; r=mod%i; L_inv[i]=(-L_inv[r]*q)%mod+mod; L_inv[i]%=mod; } ll Q; cin >> Q; ll m,U,V,W,B; ll b1,b2,b3,b4; ll s1,s2,s3,s4; ll L,l_inv; ll X; for (int q=0; q<Q; q++){ cin >> m >> U >> V >> W; if (U>V) swap(U,V); if (m==0){ cin >> B; b1=B; b2=(b1*B)%mod; b3=(b2*B)%mod; b4=(b3*B)%mod; ; if (U<W && W<V){ for (int t=U; U<=t && t<=V; t++){ A[t][1]=b1; A[t][2]=b2; A[t][3]=b3; A[t][4]=b4; } }else{ for (int t=1; t<=U; t++){ A[t][1]=b1; A[t][2]=b2; A[t][3]=b3; A[t][4]=b4; } for (int t=V; t<=N; t++){ A[t][1]=b1; A[t][2]=b2; A[t][3]=b3; A[t][4]=b4; } } } else if (m==1){ cout << 0 << endl; }else{ s1=s2=s3=s4=0; if (U<W && W<V){ L=V-U+1; for (int t=U; U<=t && t<=V; t++){ s1+=A[t][1]; s2+=A[t][2]; s3+=A[t][3]; s4+=A[t][4]; } }else{ L=U+(N-V+1); for (int t=1; t<=U; t++){ s1+=A[t][1]; s2+=A[t][2]; s3+=A[t][3]; s4+=A[t][4]; } for (int t=V; t<=N; t++){ s1+=A[t][1]; s2+=A[t][2]; s3+=A[t][3]; s4+=A[t][4]; } } s1%=mod; s2%=mod; s3%=mod; s4%=mod; l_inv=L_inv[L]; if (m==2) X=second(s1,s2,l_inv); else if (m==3) X=third(s1,s2,s3,l_inv); else X=forth(s1,s2,s3,s4,l_inv); X*=l_inv; X%=mod; cout << X << endl; } } }