結果
| 問題 | No.2369 Some Products |
| ユーザー |
 momoyuu
|
| 提出日時 | 2023-10-26 12:26:24 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 141 ms / 2,500 ms |
| コード長 | 7,733 bytes |
| コンパイル時間 | 3,575 ms |
| コンパイル使用メモリ | 263,448 KB |
| 実行使用メモリ | 69,584 KB |
| 最終ジャッジ日時 | 2023-10-26 12:26:30 |
| 合計ジャッジ時間 | 5,438 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,348 KB |
| testcase_01 | AC | 2 ms
4,348 KB |
| testcase_02 | AC | 141 ms
69,584 KB |
| testcase_03 | AC | 141 ms
69,584 KB |
| testcase_04 | AC | 140 ms
69,584 KB |
| testcase_05 | AC | 12 ms
8,096 KB |
| testcase_06 | AC | 126 ms
69,528 KB |
| testcase_07 | AC | 11 ms
8,436 KB |
| testcase_08 | AC | 26 ms
15,792 KB |
| testcase_09 | AC | 9 ms
6,992 KB |
| testcase_10 | AC | 49 ms
26,968 KB |
| testcase_11 | AC | 94 ms
53,424 KB |
| testcase_12 | AC | 7 ms
5,820 KB |
| testcase_13 | AC | 60 ms
32,528 KB |
| testcase_14 | AC | 68 ms
37,788 KB |
ソースコード
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#include<atcoder/modint>
using mint = atcoder::modint998244353;
#line 2 "misc/fastio.hpp"
#include <cstdio>
#include <cstring>
#include <string>
#include <type_traits>
#include <utility>
using namespace std;
#line 2 "internal/internal-type-traits.hpp"
#line 4 "internal/internal-type-traits.hpp"
using namespace std;
namespace internal {
template <typename T>
using is_broadly_integral =
typename conditional_t<is_integral_v<T> || is_same_v<T, __int128_t> ||
is_same_v<T, __uint128_t>,
true_type, false_type>::type;
template <typename T>
using is_broadly_signed =
typename conditional_t<is_signed_v<T> || is_same_v<T, __int128_t>,
true_type, false_type>::type;
template <typename T>
using is_broadly_unsigned =
typename conditional_t<is_unsigned_v<T> || is_same_v<T, __uint128_t>,
true_type, false_type>::type;
#define ENABLE_VALUE(x) \
template <typename T> \
constexpr bool x##_v = x<T>::value;
ENABLE_VALUE(is_broadly_integral);
ENABLE_VALUE(is_broadly_signed);
ENABLE_VALUE(is_broadly_unsigned);
#undef ENABLE_VALUE
#define ENABLE_HAS_TYPE(var) \
template <class, class = void> \
struct has_##var : false_type {}; \
template <class T> \
struct has_##var<T, void_t<typename T::var>> : true_type {}; \
template <class T> \
constexpr auto has_##var##_v = has_##var<T>::value;
#define ENABLE_HAS_VAR(var) \
template <class, class = void> \
struct has_##var : false_type {}; \
template <class T> \
struct has_##var<T, void_t<decltype(T::var)>> : true_type {}; \
template <class T> \
constexpr auto has_##var##_v = has_##var<T>::value;
} // namespace internal
#line 12 "misc/fastio.hpp"
namespace fastio {
static constexpr int SZ = 1 << 17;
static constexpr int offset = 64;
char inbuf[SZ], outbuf[SZ];
int in_left = 0, in_right = 0, out_right = 0;
struct Pre {
char num[40000];
constexpr Pre() : num() {
for (int i = 0; i < 10000; i++) {
int n = i;
for (int j = 3; j >= 0; j--) {
num[i * 4 + j] = n % 10 + '0';
n /= 10;
}
}
}
} constexpr pre;
void load() {
int len = in_right - in_left;
memmove(inbuf, inbuf + in_left, len);
in_right = len + fread(inbuf + len, 1, SZ - len, stdin);
in_left = 0;
}
void flush() {
fwrite(outbuf, 1, out_right, stdout);
out_right = 0;
}
void skip_space() {
if (in_left + offset > in_right) load();
while (inbuf[in_left] <= ' ') in_left++;
}
void single_read(char& c) {
if (in_left + offset > in_right) load();
skip_space();
c = inbuf[in_left++];
}
void single_read(string& S) {
skip_space();
while (true) {
if (in_left == in_right) load();
int i = in_left;
for (; i != in_right; i++) {
if (inbuf[i] <= ' ') break;
}
copy(inbuf + in_left, inbuf + i, back_inserter(S));
in_left = i;
if (i != in_right) break;
}
}
template <typename T,
enable_if_t<internal::is_broadly_integral_v<T>>* = nullptr>
void single_read(T& x) {
if (in_left + offset > in_right) load();
skip_space();
char c = inbuf[in_left++];
[[maybe_unused]] bool minus = false;
if constexpr (internal::is_broadly_signed_v<T>) {
if (c == '-') minus = true, c = inbuf[in_left++];
}
x = 0;
while (c >= '0') {
x = x * 10 + (c & 15);
c = inbuf[in_left++];
}
if constexpr (internal::is_broadly_signed_v<T>) {
if (minus) x = -x;
}
}
void rd() {}
template <typename Head, typename... Tail>
void rd(Head& head, Tail&... tail) {
single_read(head);
rd(tail...);
}
void single_write(const char& c) {
if (out_right > SZ - offset) flush();
outbuf[out_right++] = c;
}
void single_write(const bool& b) {
if (out_right > SZ - offset) flush();
outbuf[out_right++] = b ? '1' : '0';
}
void single_write(const string& S) {
flush(), fwrite(S.data(), 1, S.size(), stdout);
}
void single_write(const char* p) { flush(), fwrite(p, 1, strlen(p), stdout); }
template <typename T,
enable_if_t<internal::is_broadly_integral_v<T>>* = nullptr>
void single_write(const T& _x) {
if (out_right > SZ - offset) flush();
if (_x == 0) {
outbuf[out_right++] = '0';
return;
}
T x = _x;
if constexpr (internal::is_broadly_signed_v<T>) {
if (x < 0) outbuf[out_right++] = '-', x = -x;
}
constexpr int buffer_size = sizeof(T) * 10 / 4;
char buf[buffer_size];
int i = buffer_size;
while (x >= 10000) {
i -= 4;
memcpy(buf + i, pre.num + (x % 10000) * 4, 4);
x /= 10000;
}
if (x < 100) {
if (x < 10) {
outbuf[out_right] = '0' + x;
++out_right;
} else {
uint32_t q = (uint32_t(x) * 205) >> 11;
uint32_t r = uint32_t(x) - q * 10;
outbuf[out_right] = '0' + q;
outbuf[out_right + 1] = '0' + r;
out_right += 2;
}
} else {
if (x < 1000) {
memcpy(outbuf + out_right, pre.num + (x << 2) + 1, 3);
out_right += 3;
} else {
memcpy(outbuf + out_right, pre.num + (x << 2), 4);
out_right += 4;
}
}
memcpy(outbuf + out_right, buf + i, buffer_size - i);
out_right += buffer_size - i;
}
void wt() {}
template <typename Head, typename... Tail>
void wt(const Head& head, const Tail&... tail) {
single_write(head);
wt(forward<const Tail>(tail)...);
}
template <typename... Args>
void wtn(const Args&... x) {
wt(forward<const Args>(x)...);
wt('\n');
}
struct Dummy {
Dummy() { atexit(flush); }
} dummy;
} // namespace fastio
using fastio::rd;
using fastio::skip_space;
using fastio::wt;
using fastio::wtn;
mint ans[5010];
mint p[5010];
int le[5010],ri[5010],k[5010];
void solve(int l,int r,vector<int>&idx){
if(r-l==1){
for(int i = 0;i<idx.size();i++){
int ni = idx[i];
ans[ni] = p[l];
}
return;
}
int mid = (r+l)>>1;
vector<vector<mint>> left(mid-l+1,vector<mint>(mid-l+1,0));
vector<vector<mint>> right(r-mid+1,vector<mint>(r-mid+1,0));
left[mid-l][0] = 1;
for(int i = mid-1;i>=l;i--){
int ni = i - l;
for(int j = mid-l;j>=0;j--){
left[ni][j] = left[ni+1][j];
if(j-1>=0) left[ni][j] += left[ni+1][j-1] * p[i];
}
}
right[0][0] = 1;
for(int i = mid;i<r;i++){
int ni = i - mid + 1;
for(int j = r-mid;j>=0;j--){
right[ni][j] = right[ni-1][j];
if(j-1>=0) right[ni][j] += right[ni-1][j-1] * p[i];
}
}
vector<int> ls,rs;
for(int i = 0;i<idx.size();i++){
int ni = idx[i];
if(ri[ni]<=mid) ls.push_back(ni);
else if(mid<=le[ni]) rs.push_back(ni);
else{
for(int j = 0;j<=k[ni];j++){
int nni = le[ni] - l;
int nnj = ri[ni] - mid;
if(j>=mid-l+1||k[ni]-j>=r-mid+1) continue;
ans[ni] += left[nni][j] * right[nnj][k[ni]-j];
}
}
}
solve(l,mid,ls);
solve(mid,r,rs);
}
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n;
rd(n);
for(int i = 0;i<n;i++){
ll a;
rd(a);
p[i] = a;
}
int q;
rd(q);
vector<int> idx(q);
for(int i = 0;i<q;i++){
idx[i] = i;
rd(le[i],ri[i],k[i]);
le[i]--;
}
solve(0,n,idx);
for(int i = 0;i<q;i++) wtn(ans[i].val());
}