結果

問題 No.1548 [Cherry 2nd Tune B] 貴方と私とサイクルとモーメント
ユーザー 👑 KazunKazun
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
        }
    }
    
}
0