結果
問題 | No.2369 Some Products |
ユーザー |
![]() |
提出日時 | 2023-06-28 01:38:26 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,800 bytes |
コンパイル時間 | 3,381 ms |
コンパイル使用メモリ | 234,588 KB |
実行使用メモリ | 108,320 KB |
最終ジャッジ日時 | 2024-07-07 08:06:50 |
合計ジャッジ時間 | 7,246 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 1 TLE * 1 -- * 12 |
ソースコード
#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';}}