結果

問題 No.1548 [Cherry 2nd Tune B] 貴方と私とサイクルとモーメント
ユーザー KazunKazun
提出日時 2021-04-30 22:57:40
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
24,064 KB
testcase_01 AC 2 ms
10,624 KB
testcase_02 AC 3,662 ms
16,000 KB
testcase_03 AC 533 ms
26,240 KB
testcase_04 AC 4,249 ms
21,120 KB
testcase_05 AC 35 ms
24,064 KB
testcase_06 AC 2,014 ms
14,080 KB
testcase_07 AC 3,613 ms
37,328 KB
testcase_08 AC 4,055 ms
16,512 KB
testcase_09 AC 2,010 ms
15,140 KB
testcase_10 AC 2,210 ms
20,096 KB
testcase_11 AC 3,128 ms
34,084 KB
testcase_12 AC 642 ms
10,624 KB
testcase_13 AC 718 ms
33,820 KB
testcase_14 AC 1,387 ms
11,648 KB
testcase_15 AC 514 ms
25,792 KB
testcase_16 AC 3,321 ms
17,664 KB
testcase_17 TLE -
testcase_18 AC 3,814 ms
36,224 KB
testcase_19 AC 733 ms
13,764 KB
testcase_20 AC 1,760 ms
21,504 KB
testcase_21 AC 1,844 ms
27,648 KB
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
testcase_30 TLE -
testcase_31 TLE -
testcase_32 AC 102 ms
18,720 KB
testcase_33 TLE -
testcase_34 TLE -
testcase_35 TLE -
testcase_36 TLE -
testcase_37 TLE -
testcase_38 AC 104 ms
18,688 KB
testcase_39 TLE -
testcase_40 TLE -
testcase_41 TLE -
権限があれば一括ダウンロードができます

ソースコード

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