結果

問題 No.2369 Some Products
ユーザー Kak1_n0_taneKak1_n0_tane
提出日時 2023-06-28 01:38:26
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,800 bytes
コンパイル時間 3,861 ms
コンパイル使用メモリ 232,484 KB
実行使用メモリ 8,760 KB
最終ジャッジ日時 2023-09-21 14:20:35
合計ジャッジ時間 7,923 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 TLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;

istream &operator>>(istream &is, modint998244353 &a) { long long v; is >> v; a = v; return is; }
ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); }
istream &operator>>(istream &is, modint1000000007 &a) { long long v; is >> v; a = v; return is; }
ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); }
template<int m> istream &operator>>(istream &is, static_modint<m> &a) { long long v; is >> v; a = v; return is; }
template<int m> istream &operator>>(istream &is, dynamic_modint<m> &a) { long long v; is >> v; a = v; return is; }
template<int m> ostream &operator<<(ostream &os, const static_modint<m> &a) { return os << a.val(); }
template<int m> ostream &operator<<(ostream &os, const dynamic_modint<m> &a) { return os << a.val(); }
#define rep_(i, a_, b_, a, b, ...) for (int i = (a), lim##i = (b); i < lim##i; ++i)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define drep_(i, a_, b_, a, b, ...) for (int i = (a)-1, lim##i = (b); i >= lim##i; --i)
#define drep(i, ...) drep_(i, __VA_ARGS__, __VA_ARGS__, __VA_ARGS__, 0)
using ll = long long;
template<class T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; }
template<class T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; }
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;

using mint = modint998244353;

int main(){
    // FILE *out = freopen("out1.txt", "w", stdout);
    int N;
    cin >> N;
    vector<ll> P(N);
    rep(i,N) cin >> P[i];

    // func[B][X] := 1以上B以下の整数からX個選び、積の総和
    vector<vector<mint>> func(N+1, vector<mint>(N+1, 0));
    rep(x,N+1){
        if(x==0) continue;
        rep(b,N){
            if(x==1){
                func[b+1][1] = func[b][1] + P[b];
            }
            else{
                func[b+1][x] = func[b][x] + P[b]*func[b][x-1];
            }
        }
    }
    /*
    rep(i,N+1){
        rep(j,N+1){
            cout << func[i][j] << (j==N?'\n':' ');
        }
    }
    */

    int Q;
    cin >> Q;

    while(Q--){
        int A, B, X;
        cin >> A >> B >> X;
        vector<mint> Vec_A_B_n(B+1, 1), Vec_1_A_1_n(B+1, 1), Vec_1_B_n(B+1, 1);
        for(int i=0;i<=B;i++){
            Vec_1_A_1_n[i] = func[A-1][i];
            Vec_1_B_n[i] = func[B][i];
        }
        for(int i=1;i<=B;i++){
            Vec_A_B_n[i] = Vec_1_B_n[i];
            for(int j=0;j<i;j++){
                Vec_A_B_n[i] -= Vec_1_A_1_n[i-j] * Vec_A_B_n[j];
            }
        }
        cout << Vec_A_B_n[X] << '\n';
    }
}
0