結果
| 問題 |
No.1067 #いろいろな色 / Red and Blue and more various colors (Middle)
|
| コンテスト | |
| ユーザー |
 keijak
|
| 提出日時 | 2020-10-23 08:47:35 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 200 ms / 2,000 ms |
| コード長 | 6,305 bytes |
| コンパイル時間 | 3,363 ms |
| コンパイル使用メモリ | 239,300 KB |
| 最終ジャッジ日時 | 2025-01-15 12:45:50 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 25 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/convolution>
#include <atcoder/modint>
using i64 = long long;
using u64 = unsigned long long;
#define REP(i, n) for (int i = 0, REP_N_ = int(n); i < REP_N_; ++i)
#define ALL(x) std::begin(x), std::end(x)
template <class T>
inline bool chmax(T &a, T b) {
return a < b and ((a = std::move(b)), true);
}
template <class T>
inline bool chmin(T &a, T b) {
return a > b and ((a = std::move(b)), true);
}
template <typename T>
using V = std::vector<T>;
template <typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &a) {
for (auto &x : a) is >> x;
return is;
}
template <typename Container>
std::ostream &pprint(const Container &a, std::string_view sep = " ",
std::string_view ends = "\n", std::ostream *os = nullptr) {
if (os == nullptr) os = &std::cout;
auto b = std::begin(a), e = std::end(a);
for (auto it = std::begin(a); it != e; ++it) {
if (it != b) *os << sep;
*os << *it;
}
return *os << ends;
}
template <typename T, typename = void>
struct is_iterable : std::false_type {};
template <typename T>
struct is_iterable<T, std::void_t<decltype(std::begin(std::declval<T>())),
decltype(std::end(std::declval<T>()))>>
: std::true_type {};
template <typename T,
typename = std::enable_if_t<is_iterable<T>::value &&
!std::is_same<T, std::string>::value>>
std::ostream &operator<<(std::ostream &os, const T &a) {
return pprint(a, ", ", "", &(os << "{")) << "}";
}
template <typename T, typename U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &a) {
return os << "(" << a.first << ", " << a.second << ")";
}
#ifdef ENABLE_DEBUG
template <typename T>
void pdebug(const T &value) {
std::cerr << value;
}
template <typename T, typename... Ts>
void pdebug(const T &value, const Ts &... args) {
pdebug(value);
std::cerr << ", ";
pdebug(args...);
}
#define DEBUG(...) \
do { \
std::cerr << " \033[33m (L" << __LINE__ << ") "; \
std::cerr << #__VA_ARGS__ << ":\033[0m "; \
pdebug(__VA_ARGS__); \
std::cerr << std::endl; \
} while (0)
#else
#define pdebug(...)
#define DEBUG(...)
#endif
using namespace std;
// Formal Power Series (dense format).
template <typename T, int DMAX>
struct DenseFPS {
// Coefficients of terms from x^0 to x^DMAX.
std::vector<T> coeff_;
DenseFPS() : coeff_(1) {} // zero-initialized
explicit DenseFPS(std::vector<T> c) : coeff_(std::move(c)) {
assert((int)c.size() <= DMAX + 1);
}
DenseFPS(const DenseFPS &other) : coeff_(other.coeff_) {}
DenseFPS(DenseFPS &&other) : coeff_(std::move(other.coeff_)) {}
DenseFPS &operator=(const DenseFPS &other) {
coeff_ = other.coeff_;
return *this;
}
DenseFPS &operator=(DenseFPS &&other) {
coeff_ = std::move(other.coeff_);
return *this;
}
int size() const { return (int)coeff_.size(); }
// Returns the coefficient of x^d.
T operator[](int d) const {
if (d >= size()) return 0;
return coeff_[d];
}
DenseFPS &operator+=(const T &scalar) {
coeff_[0] += scalar;
return *this;
}
friend DenseFPS operator+(const DenseFPS &x, const T &scalar) {
DenseFPS res = x;
res += scalar;
return res;
}
DenseFPS &operator+=(const DenseFPS &other) {
if (size() < other.size()) {
coeff_.resize(other.size());
}
for (int i = 0; i < other.size(); ++i) coeff_[i] += other[i];
return *this;
}
friend DenseFPS operator+(const DenseFPS &x, const DenseFPS &y) {
DenseFPS res = x;
res += y;
return res;
}
DenseFPS &operator-=(const DenseFPS &other) {
if (size() < other.size()) {
coeff_.resize(other.size());
}
for (int i = 0; i < other.size(); ++i) coeff_[i] -= other[i];
return *this;
}
friend DenseFPS operator-(const DenseFPS &x, const DenseFPS &y) {
DenseFPS res = x;
res -= y;
return res;
}
DenseFPS &operator*=(const T &scalar) {
for (auto &x : coeff_) x *= scalar;
return *this;
}
friend DenseFPS operator*(const DenseFPS &x, const T &scalar) {
DenseFPS res = x;
res *= scalar;
return res;
}
DenseFPS &operator*=(const DenseFPS &other) {
*this = this->mul_naive(other);
return *this;
}
friend DenseFPS operator*(const DenseFPS &x, const DenseFPS &y) {
return x.mul_naive(y);
}
private:
// Naive multiplication. O(N^2)
DenseFPS mul_naive(const DenseFPS &other) const {
const int n = min(size() + other.size() - 1, DMAX + 1);
DenseFPS res;
res.coeff_.resize(n);
for (int i = 0; i < size(); ++i) {
for (int j = 0; j < other.size(); ++j) {
if (i + j >= n) break;
res.coeff_[i + j] += (*this)[i] * other[j];
}
}
return res;
}
};
namespace fps {
// Fast polynomial multiplication by single NTT.
template <typename ModInt, int DMAX>
DenseFPS<ModInt, DMAX> mul_ntt(const DenseFPS<ModInt, DMAX> &x,
const DenseFPS<ModInt, DMAX> &y) {
static_assert(ModInt::mod() != 1'000'000'007); // Must be a NTT-friendly MOD!
auto z = atcoder::convolution(x.coeff_, y.coeff_);
if (z.size() > DMAX + 1) {
z.resize(DMAX + 1);
}
return DenseFPS<ModInt, DMAX>(std::move(z));
}
} // namespace fps
using mint = atcoder::modint998244353;
const int MOD = 998244353;
const int PMAX = 6'000;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
cin >> N >> Q;
V<int> A(N);
cin >> A;
sort(ALL(A));
V<DenseFPS<mint, PMAX>> ps(N + 1);
V<mint> prods(N + 1);
prods[0] = 1;
REP(i, N) prods[i + 1] = prods[i] * A[i];
DenseFPS<mint, PMAX> f;
f += 1;
ps[N] = f;
REP(i, N) {
int ri = N - 1 - i;
DenseFPS<mint, PMAX> g(std::vector<mint>(2));
g.coeff_[0] = A[ri] - 1;
g.coeff_[1] = 1;
ps[ri] = fps::mul_ntt(ps[ri + 1], g);
}
REP(i, Q) {
int l, r, p;
cin >> l >> r >> p;
u64 ans = 0;
for (int x = l; x <= r; ++x) {
int j = lower_bound(A.begin(), A.end(), x) - A.begin();
mint count = ps[j][p] * prods[j];
ans ^= count.val();
}
ans %= MOD;
cout << ans << '\n';
}
}