結果

問題 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
コンパイル時間 890 ms
コンパイル使用メモリ 77,764 KB
実行使用メモリ 25,624 KB
最終ジャッジ日時 2024-05-08 16:17:27
合計ジャッジ時間 51,944 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
25,624 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 3,632 ms
10,616 KB
testcase_03 AC 549 ms
7,424 KB
testcase_04 AC 4,035 ms
15,744 KB
testcase_05 AC 33 ms
6,940 KB
testcase_06 AC 2,008 ms
8,704 KB
testcase_07 AC 3,374 ms
18,600 KB
testcase_08 AC 3,936 ms
11,264 KB
testcase_09 AC 1,987 ms
8,320 KB
testcase_10 AC 2,250 ms
14,800 KB
testcase_11 AC 3,047 ms
15,360 KB
testcase_12 AC 631 ms
6,940 KB
testcase_13 AC 715 ms
15,072 KB
testcase_14 AC 1,418 ms
6,940 KB
testcase_15 AC 478 ms
18,784 KB
testcase_16 AC 3,121 ms
12,288 KB
testcase_17 TLE -
testcase_18 AC 3,623 ms
17,520 KB
testcase_19 AC 719 ms
6,944 KB
testcase_20 AC 1,669 ms
16,080 KB
testcase_21 AC 1,811 ms
9,088 KB
testcase_22 TLE -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
権限があれば一括ダウンロードができます

ソースコード

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