結果

問題 No.2369 Some Products
ユーザー maksimmaksim
提出日時 2023-07-01 00:13:43
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 123 ms / 2,500 ms
コード長 1,834 bytes
コンパイル時間 2,087 ms
コンパイル使用メモリ 176,936 KB
実行使用メモリ 84,356 KB
最終ジャッジ日時 2023-09-21 18:10:53
合計ジャッジ時間 3,705 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 123 ms
78,760 KB
testcase_03 AC 123 ms
78,884 KB
testcase_04 AC 123 ms
78,852 KB
testcase_05 AC 13 ms
10,656 KB
testcase_06 AC 102 ms
84,356 KB
testcase_07 AC 11 ms
11,052 KB
testcase_08 AC 25 ms
21,592 KB
testcase_09 AC 11 ms
9,044 KB
testcase_10 AC 46 ms
35,884 KB
testcase_11 AC 79 ms
65,900 KB
testcase_12 AC 7 ms
6,948 KB
testcase_13 AC 57 ms
42,960 KB
testcase_14 AC 64 ms
49,536 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int p=998244353;
const int maxn=5e3+5;
vector<int> a;
int res[maxn];
vector<int> h[maxn];
void go(vector<array<int,4> > v,int l,int r)
{
    if(v.empty())
    {
        return;
    }
    int mid=(l+r)/2;
    h[mid]={1};
    for(int i=mid-1;i>=l;--i)
    {
        h[i]=h[i+1];h[i].push_back(0);
        for(int j=0;j<h[i+1].size();++j)
        {
            h[i][j+1]+=h[i+1][j]*a[i];h[i][j+1]%=p;
        }
    }
    for(int i=mid+1;i<=r;++i)
    {
        h[i]=h[i-1];h[i].push_back(0);
        for(int j=0;j<h[i-1].size();++j)
        {
            h[i][j+1]+=h[i-1][j]*a[i-1];h[i][j+1]%=p;
        }
    }
    vector<array<int,4> > v1,v2;
    for(array<int,4> h1:v)
    {
        int l=h1[0];int r=h1[1];int k=h1[2];
        if(l<=mid && r>=mid)
        {
            vector<int> v1=h[l];vector<int> v2=h[r];
            //for(int x1:v1) cout<<x1<<' '; cout<<endl;
            //for(int x2:v2) cout<<x2<<' '; cout<<endl;
            for(int i=0;i<=k;++i)
            {
                int j=k-i;
                if(i<v1.size() && j<v2.size())
                {
                    res[h1[3]]+=(v1[i]*v2[j]);res[h1[3]]%=p;
                }
            }
        }
        else if(l<mid)
        {
            v1.push_back(h1);
        }
        else
        {
            v2.push_back(h1);
        }
    }
    go(v1,l,mid);go(v2,mid,r);
}
int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;cin>>n;
    a.resize(n);for(int i=0;i<n;++i) {cin>>a[i];a[i]%=p;a[i]+=p;a[i]%=p;}
    int q;cin>>q;
    vector<array<int,4> > v;
    for(int cyc=0;cyc<q;++cyc)
    {
        int l,r,k;cin>>l>>r>>k;--l;
        v.push_back({l,r,k,cyc});
    }
    go(v,0,n);
    for(int i=0;i<q;++i) {cout<<(res[i]%p+p)%p<<'\n';}
    return 0;
}
0