結果
| 問題 | No.1068 #いろいろな色 / Red and Blue and more various colors (Hard) |
| ユーザー |
 Egor Kulikov
|
| 提出日時 | 2020-05-29 23:00:27 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2,688 ms / 3,500 ms |
| コード長 | 24,360 bytes |
| コンパイル時間 | 2,927 ms |
| コンパイル使用メモリ | 211,180 KB |
| 最終ジャッジ日時 | 2025-01-10 18:11:06 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 29 |
コンパイルメッセージ
main.cpp:70:24: warning: ‘template<class _Category, class _Tp, class _Distance, class _Pointer, class _Reference> struct std::iterator’ is deprecated [-Wdeprecated-declarations]
70 | class NumberIterator : iterator<forward_iterator_tag, int> {
| ^~~~~~~~
In file included from /usr/include/c++/13/bits/stl_algobase.h:65,
from /usr/include/c++/13/algorithm:60,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
from main.cpp:11:
/usr/include/c++/13/bits/stl_iterator_base_types.h:127:34: note: declared here
127 | struct _GLIBCXX17_DEPRECATED iterator
| ^~~~~~~~
ソースコード
/**
* code generated by JHelper
* More info: https://github.com/AlexeyDmitriev/JHelper
* @author Egor Kulikov
*/
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
using ll = long long;
using ull = unsigned long long;
using li = __int128;
using uli = unsigned __int128;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
void doReplace() {
}
template <typename T, typename U, typename...Vs>
void doReplace(T& t, const U& u, Vs&& ...vs) {
t = u;
doReplace(vs...);
}
template <typename T, typename...Us>
T minim(T& was, const T& cand, Us&& ...us) {
if (was > cand) {
was = cand;
doReplace(us...);
}
return was;
}
template <typename T, typename...Us>
T maxim(T& was, const T& cand, Us&& ...us) {
if (was < cand) {
was = cand;
doReplace(us...);
}
return was;
}
template <typename D>
D dPower(D base, ll exponent) {
if (exponent < 0) {
return dPower(1 / base, -exponent);
}
if (exponent == 0) {
return 1;
}
if ((exponent & 1) == 1) {
return dPower(base, exponent - 1) * base;
} else {
D res = dPower(base, exponent >> 1);
return res * res;
}
}
class NumberIterator : iterator<forward_iterator_tag, int> {
public:
int v;
NumberIterator(int v) : v(v) {}
operator int&() { return v; }
int operator*() { return v; }
};
class range : pii {
public:
range(int begin, int end) : pii(begin, max(begin, end)) {}
range(int n) : pii(0, max(0, n)) {}
NumberIterator begin() {
return first;
}
NumberIterator end() {
return second;
}
};
template <typename T>
class arr {
T* b;
int n;
void allocate(int sz) {
#ifdef LOCAL
if (sz < 0) {
throw "bad alloc";
}
#endif
n = sz;
if (sz > 0) {
b = (T*) (::operator new(sz * sizeof(T)));
} else {
b = nullptr;
}
}
public:
arr(int n = 0) {
allocate(n);
#ifdef LOCAL
view();
#endif
}
arr(int n, const T& init) {
allocate(n);
for (int i : range(n)) {
::new((void*) (b + i)) T(init);
}
#ifdef LOCAL
view();
#endif
}
arr(initializer_list<T> l) : arr(l.size()) {
if (n > 0) {
memcpy(b, l.begin(), n * sizeof(T));
}
}
arr(T* b, int n) : arr(b, b + n) {}
arr(T* b, T* e) : b(b), n(e - b) {}
int size() const {
return n;
}
T* begin() {
return b;
}
const T* begin() const {
return b;
}
T* end() {
return b + n;
}
const T* end() const {
return b + n;
}
arr<T> clone() const {
arr<T> res(n);
copy(b, b + n, res.begin());
return res;
}
T& operator[](int at) {
#ifdef LOCAL
if (at < 0 || at >= n) {
throw "Out of bounds";
}
#endif
return b[at];
}
const T& operator[](int at) const {
#ifdef LOCAL
if (at < 0 || at >= n) {
throw "Out of bounds";
}
#endif
return b[at];
}
bool operator==(const arr& other) const {
if (n != other.n) {
return false;
}
for (int i : range(n)) {
if (b[i] != other.b[i]) {
return false;
}
}
return true;
}
vector<T> view() {
return vector<T>(b, b + min(n, 50));
}
};
typedef arr<int> arri;
void decreaseByOne() {}
template <typename T, class...Vs>
void decreaseByOne(arr<T>& array, Vs& ...vs) {
int n = array.size();
for (int i : range(n)) {
array[i]--;
}
decreaseByOne(vs...);
}
template <typename T, typename U>
void decreaseByOne(arr<pair<T, U>>& v) {
for (auto& p : v) {
p.first--;
p.second--;
}
}
template <typename T>
class arr2d {
T* b;
int d1;
int d2;
int sz;
void allocate(int n) {
#ifdef LOCAL
if (n < 0) {
throw "bad alloc";
}
#endif
if (n > 0) {
b = (T*) (::operator new(n * sizeof(T)));
} else {
b = nullptr;
}
}
public:
arr2d(int d1 = 0, int d2 = 0) : d1(d1), d2(d2), sz(d1 * d2) {
#ifdef LOCAL
if (d1 < 0 || d2 < 0) {
throw "bad alloc";
}
#endif
allocate(sz);
#ifdef LOCAL
view();
#endif
}
arr2d(int d1, int d2, const T& init) : d1(d1), d2(d2), sz(d1 * d2) {
#ifdef LOCAL
if (d1 < 0 || d2 < 0) {
throw "bad alloc";
}
#endif
allocate(sz);
for (int i : range(sz)) {
::new((void*) (b + i)) T(init);
}
#ifdef LOCAL
view();
#endif
}
arr2d(T* b, int d1, int d2) : b(b), d1(d1), d2(d2), sz(d1 * d2) {}
int size() const {
return sz;
}
int dim1() const {
return d1;
}
int dim2() const {
return d2;
}
T* begin() {
return b;
}
T* end() {
return b + sz;
}
T& operator()(int i1, int i2) {
#ifdef LOCAL
if (i1 < 0 || i1 >= d1 || i2 < 0 || i2 >= d2) {
throw "Out of bounds";
}
#endif
return b[i1 * d2 + i2];
}
const T& operator()(int i1, int i2) const {
#ifdef LOCAL
if (i1 < 0 || i1 >= d1 || i2 < 0 || i2 >= d2) {
throw "Out of bounds";
}
#endif
return b[i1 * d2 + i2];
}
T& operator[](const pii& p) {
return operator()(p.first, p.second);
}
const T& operator[](const pii& p) const {
return operator()(p.first, p.second);
}
arr<T> operator[](int at) {
#ifdef LOCAL
if (at < 0 || at >= d1) {
throw "Out of bounds";
}
#endif
return arr<T>(b + at * d2, d2);
}
vector<vector<T>> view() {
vector<vector<T>> res(min(d1, 50));
for (int i : range(res.size())) {
res[i] = (*this)[i].view();
}
return res;
}
arr2d<T> clone() {
arr2d<T> res(d1, d2);
copy(b, b + sz, res.b);
return res;
}
};
inline bool isWhitespace(int c) {
return isspace(c) || c == EOF;
}
class Input {
private:
bool exhausted = false;
int bufSize = 4096;
char* buf = new char[bufSize];
int bufRead = 0;
int bufAt = 0;
public:
inline int get() {
if (exhausted) {
#ifdef LOCAL
throw "Input exhausted";
#endif
return EOF;
}
if (bufRead == bufAt) {
bufRead = fread(buf, sizeof(char), bufSize, stdin);
bufAt = 0;
}
if (bufRead == bufAt) {
exhausted = true;
return EOF;
}
return buf[bufAt++];
}
private:
template <typename T>
inline T readInteger() {
int c = skipWhitespace();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = get();
}
T res = 0;
do {
if (!isdigit(c)) {
#ifdef LOCAL
throw "Number format error";
#endif
return sgn * res;
}
res *= 10;
res += c - '0';
c = get();
} while (!isWhitespace(c));
return res * sgn;
}
void initArrays(int) {}
template <typename T, class...Vs>
void initArrays(int n, arr<T>& array, Vs& ...vs) {
array = arr<T>(n, T());
initArrays(n, vs...);
}
template <typename T, class...Vs>
void initArrays(int n, vector<T>&, Vs& ...vs) {
initArrays(n, vs...);
}
void readImpl(int) {}
template <typename T, class...Vs>
void readImpl(int i, arr<T>& arr, Vs& ...vs) {
arr[i] = readType<T>();
readImpl(i, vs...);
}
template <typename T, class...Vs>
void readImpl(int i, vector<T>& arr, Vs& ...vs) {
arr.push_back(readType<T>());
readImpl(i, vs...);
}
public:
inline int skipWhitespace() {
int c;
while (isWhitespace(c = get()) && c != EOF);
return c;
}
inline int readInt() {
return readInteger<int>();
}
inline ll readLong() {
return readInteger<ll>();
}
string readString() {
int c = skipWhitespace();
if (c == EOF) {
#ifdef LOCAL
throw "Input exhausted";
#endif
return "";
}
string res;
do {
res.push_back(c);
} while (!isWhitespace(c = get()));
return res;
}
arri readIntArray(int size) {
return readArray<int>(size);
}
arr<ll> readLongArray(int size) {
return readArray<ll>(size);
}
arr<double> readDoubleArray(int size) {
return readArray<double>(size);
}
arr<string> readStringArray(int size) {
return readArray<string>(size);
}
arr<char> readCharArray(int size) {
return readArray<char>(size);
}
template <typename T>
T readType() {
throw "Operation not supported";
}
template <typename U, typename V>
pair<U, V> readType() {
U first = readType<U>();
V second = readType<V>();
return make_pair(first, second);
}
template <typename T>
arr<T> readArray(int n) {
arr<T> res(n, T());
for (int i : range(n)) {
res[i] = readType<T>();
}
return res;
}
template <class...Vs>
void readArrays(int n, Vs& ...vs) {
initArrays(n, vs...);
for (int i : range(n)) {
readImpl(i, vs...);
}
}
template <typename U, typename V>
arr<pair<U, V>> readArray(int n) {
arr<pair<U, V>> res(n);
for (int i : range(n)) {
res[i] = readType<U, V>();
}
return res;
}
template <typename T>
arr2d<T> readTable(int rows, int cols) {
arr2d<T> result(rows, cols);
for (int i : range(rows)) {
for (int j : range(cols)) {
result(i, j) = readType<T>();
}
}
return result;
}
arr2d<int> readIntTable(int rows, int cols) {
return readTable<int>(rows, cols);
}
arr2d<char> readCharTable(int rows, int cols) {
return readTable<char>(rows, cols);
}
string readLine() {
int c = get();
if (c == EOF) {
#ifdef LOCAL
throw "Input exhausted";
#endif
return "";
}
string res;
do {
res.push_back(c);
c = get();
} while (c != '\n' && c != '\r' && c != EOF);
return res;
}
inline double readDouble() {
int c = skipWhitespace();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = get();
}
double res = 0;
do {
if (tolower(c) == 'e') {
return sgn * res * dPower(double(10), readInt());
}
if (!isdigit(c)) {
#ifdef LOCAL
throw "Number format error";
#endif
return sgn * res;
}
res *= 10;
res += c - '0';
c = get();
} while (!isWhitespace(c) && c != '.');
if (c == '.') {
double add = 0;
int length = 0;
c = get();
do {
if (tolower(c) == 'e') {
return sgn * (res + add * dPower(double(10), -length)) * dPower(double(10), readInt());
}
if (!isdigit(c)) {
#ifdef LOCAL
throw "Number format error";
#endif
res += add * dPower(10, -length);
return res * sgn;
}
add *= 10;
add += c - '0';
length++;
c = get();
} while (!isWhitespace(c));
res += add * dPower(double(10), -length);
}
return res * sgn;
}
inline char readChar() {
int c = skipWhitespace();
if (c == EOF) {
#ifdef LOCAL
throw "Input exhausted";
#endif
return 0;
}
return c;
}
inline bool isExhausted() { return exhausted; }
inline void setBufSize(int newBufSize) {
if (newBufSize > bufSize) {
char* newBuf = new char[newBufSize];
memcpy(newBuf, buf, bufSize);
buf = newBuf;
}
bufSize = newBufSize;
}
};
template <>
inline double Input::readType() {
return readDouble();
}
template <>
inline int Input::readType() {
return readInt();
}
template <>
inline ll Input::readType() {
return readLong();
}
template <>
inline char Input::readType() {
return readChar();
}
template <>
inline string Input::readType() {
return readString();
}
Input in;
class Output {
private:
ostream* out;
template <typename T>
inline void printSingle(const T& value) {
*out << value;
}
template <typename T>
void printSingle(const vector<T>& array) {
size_t n = array.size();
for (int i : range(n)) {
*out << array[i];
if (i + 1 != n) {
*out << ' ';
}
}
}
template <typename T>
void printSingle(const arr<T>& array) {
int n = array.size();
for (int i : range(n)) {
*out << array[i];
if (i + 1 != n) {
*out << ' ';
}
}
}
template <typename T>
void printSingle(const arr2d<T>& array) {
size_t n = array.dim1();
size_t m = array.dim2();
for (int i : range(n)) {
for (int j : range(m)) {
*out << array(i, j);
if (j + 1 != m) {
*out << ' ';
}
}
if (i + 1 != n) {
*out << '\n';
}
}
}
template <typename T, typename U>
inline void printSingle(const pair<T, U>& value) {
out << value.first << ' ' << value.second;
}
public:
bool autoflush;
Output(ostream& out, bool autoflush) : out(&out), autoflush(autoflush) {
setPrecision(20);
}
void setOut(ostream& nOut) {
out = &nOut;
setPrecision(20);
}
inline void print() {}
template <typename T, typename...Targs>
inline void print(const T& first, const Targs... args) {
printSingle(first);
if (sizeof...(args) != 0) {
*out << ' ';
print(args...);
}
if (autoflush) {
flush();
}
}
template <typename...Targs>
inline void printLine(const Targs... args) {
print(args...);
*out << '\n';
if (autoflush) {
flush();
}
}
inline void flush() {
out->flush();
}
inline void setPrecision(int digs) {
*out << fixed << setprecision(digs);
}
};
Output out(cout, false);
Output err(cerr, true);
template <typename T>
class RecursiveFunction {
T t;
public:
RecursiveFunction(T&& t) : t(forward<T>(t)) {}
template <typename... Args>
auto operator()(Args&& ... args) const {
return t(*this, forward<Args>(args)...);
}
};
const int MOD7 = 1000000007;
const int MOD9 = 1000000009;
const int MODF = 998244353;
int mod = MOD7;
ll gcd(ll a, ll b, ll& x, ll& y) {
if (a == 0) {
x = 0;
y = 1;
return b;
}
int d = gcd(b % a, a, y, x);
x -= (b / a) * y;
return d;
}
class modint {
public:
int n;
modint() : n(0) {}
modint(ll n, bool special = false) {
if (special) {
this->n = -1;
return;
}
if (n >= 0 && n < mod) {
this->n = n;
return;
}
n %= mod;
if (n < 0) {
n += mod;
}
this->n = n;
}
modint& operator+=(const modint& other) {
#ifdef LOCAL
if (n == -1 || other.n == -1) {
throw "Illegal state";
}
#endif
n += other.n;
if (n >= mod) {
n -= mod;
}
return *this;
}
modint& operator-=(const modint& other) {
#ifdef LOCAL
if (n == -1 || other.n == -1) {
throw "Illegal state";
}
#endif
n -= other.n;
if (n < 0) {
n += mod;
}
return *this;
}
modint& operator*=(const modint& other) {
#ifdef LOCAL
if (n == -1 || other.n == -1) {
throw "Illegal state";
}
#endif
n = ll(n) * other.n % mod;
return *this;
}
modint& operator/=(const modint& other) {
#ifdef LOCAL
if (other.n == 0) {
throw "Division by zero";
}
if (n == -1 || other.n == -1) {
throw "Illegal state";
}
#endif
return *this *= other.inverse();
}
modint operator-() {
#ifdef LOCAL
if (n == -1) {
throw "Illegal state";
}
#endif
if (n == 0) {
return 0;
}
return modint(mod - n);
}
modint inverse() const {
#ifdef LOCAL
if (n == -1) {
throw "Illegal state";
}
#endif
ll x, y;
ll g = gcd(ll(n), ll(mod), x, y);
#ifdef LOCAL
if (g != 1) {
throw "not inversable";
}
#endif
return x;
}
int log(modint alpha);
};
modint nullModint(-1, true);
modint operator+(const modint& a, const modint& b) {
return modint(a) += b;
}
modint operator-(const modint& a, const modint& b) {
return modint(a) -= b;
}
modint operator*(const modint& a, const modint& b) {
return modint(a) *= b;
}
modint operator/(const modint& a, const modint& b) {
return modint(a) /= b;
}
ostream& operator<<(ostream& out, const modint& val) {
return out << val.n;
}
bool operator==(const modint& a, const modint& b) {
return a.n == b.n;
}
bool operator!=(const modint& a, const modint& b) {
return a.n != b.n;
}
namespace std {
template <>
struct hash<modint> {
size_t operator()(const modint& n) const {
return n.n;
}
};
}
int modint::log(modint alpha) {
#ifdef LOCAL
if (n == -1 || alpha.n == -1) {
throw "Illegal state";
}
#endif
unordered_map<modint, int> base;
int exp = 0;
modint pow = 1;
modint inv = *this;
modint alInv = alpha.inverse();
while (exp * exp < mod) {
if (inv == 1) {
return exp;
}
base[inv] = exp++;
pow *= alpha;
inv *= alInv;
}
modint step = pow;
for (int i = 1;; i++) {
if (base.count(pow)) {
return exp * i + base[pow];
}
pow *= step;
}
}
template <typename T>
T gcd(T a, T b) {
a = abs(a);
b = abs(b);
while (b != 0) {
a = a % b;
swap(a, b);
}
return a;
}
template <typename T>
T lcm(T a, T b) {
return a / gcd(a, b) * b;
}
template <typename T>
T power(const T& a, ll b) {
if (b == 0) {
return 1;
}
if ((b & 1) == 0) {
T res = power(a, b >> 1);
return res * res;
} else {
return power(a, b - 1) * a;
}
}
template <typename T>
T factorial(int n) {
T result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
template <typename T>
arr<T> factorials(int length) {
arr<T> result(length);
if (length > 0) {
result[0] = 1;
}
for (int i = 1; i < length; i++) {
result[i] = result[i - 1] * i;
}
return result;
}
template <typename T>
arr<T> powers(T base, int length) {
arr<T> result(length);
if (length > 0) {
result[0] = 1;
}
for (int i = 1; i < length; i++) {
result[i] = result[i - 1] * base;
}
return result;
}
namespace prime_fft {
bool init = false;
modint root;
modint reverseRoot;
int rootPower;
vector<modint> aa;
vector<modint> bb;
}
void initPrimeFFT() {
if (prime_fft::init) {
return;
}
prime_fft::init = true;
prime_fft::rootPower = 1;
int pw = 0;
while ((mod - 1) % (2 * prime_fft::rootPower) == 0) {
prime_fft::rootPower *= 2;
pw++;
}
for (int i = 2;; i++) {
mod--;
int exp = power(modint(2), pw - 1).n;
int next = (exp * 2) % mod;
mod++;
if (power(modint(i), exp).n != 1 && power(modint(i), next).n == 1) {
prime_fft::root = i;
prime_fft::reverseRoot = prime_fft::root.inverse();
break;
}
}
}
namespace prime_fft {
void primeFFT(vector<modint>& array, bool invert, int n) {
for (int i = 1, j = 0; i < n; ++i) {
int bit = n >> 1;
for (; j >= bit; bit >>= 1) {
j -= bit;
}
j += bit;
if (i < j) {
swap(array[i], array[j]);
}
}
for (int len = 2; len <= n; len <<= 1) {
modint wlen = invert ? reverseRoot : root;
for (int i = len; i < rootPower; i <<= 1) {
wlen *= wlen;
}
int half = len >> 1;
for (int i = 0; i < n; i += len) {
modint w = 1;
for (int j = 0; j < half; ++j) {
modint u = array[i + j], v = array[i + j + half] * w;
array[i + j] = u + v;
array[i + j + half] = u - v;
w *= wlen;
}
}
}
if (invert) {
modint reverseSize = modint(n).inverse();
for (int i = 0; i < n; ++i) {
array[i] *= reverseSize;
}
}
}
}
template <typename It>
void multiply(const It fBegin, const It fEnd, const It sBegin, const It sEnd, It res) {
initPrimeFFT();
unsigned long fLen = fEnd - fBegin;
unsigned long sLen = sEnd - sBegin;
int resLen = fLen + sLen - 1;
if (resLen <= 100) {
fill(res, res + resLen, 0);
for (int i = 0; i < fLen; i++) {
for (int j = 0; j < sLen; j++) {
res[i + j] += fBegin[i] * sBegin[j];
}
}
return;
}
int resultSize = 1;
while (resultSize < resLen) {
resultSize *= 2;
}
vector<modint>& aa = prime_fft::aa;
vector<modint>& bb = prime_fft::bb;
if (aa.size() < resultSize) {
aa.resize(resultSize);
bb.resize(resultSize);
}
fill(aa.begin() + fLen, aa.begin() + resultSize, modint(0));
fill(bb.begin() + sLen, bb.begin() + resultSize, modint(0));
copy(fBegin, fEnd, aa.begin());
copy(sBegin, sEnd, bb.begin());
prime_fft::primeFFT(aa, false, resultSize);
if (equal(fBegin, fEnd, sBegin, sEnd)) {
copy(all(aa), bb.begin());
} else {
prime_fft::primeFFT(bb, false, resultSize);
}
for (int i = 0; i < resultSize; i++) {
aa[i] *= bb[i];
}
prime_fft::primeFFT(aa, true, resultSize);
for (int i = 0; i < resLen; i++) {
res[i] = aa[i];
}
}
vector<modint> multiply(vector<modint>&& first, vector<modint>&& second) {
auto len = first.size() + second.size() - 1;
vector<modint> res(len);
multiply(all(first), all(second), res.begin());
return res;
}
class d {
public:
void solve() {
int n = in.readInt();
int q = in.readInt();
auto a = in.readLongArray(n);
mod = MODF;
initPrimeFFT();
RecursiveFunction rec = [&](const auto& self, int from, int to) -> vector<modint> {
if (from + 1 == to) {
return {a[from] - 1, 1};
}
int mid = (from + to) / 2;
return multiply(self(from, mid), self(mid, to));
};
auto res = rec(0, n);
for (int z : range(q)) {
out.printLine(res[in.readInt()]);
}
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
#ifdef LOCAL_RELEASE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
auto time = clock();
#endif
d solver;
solver.solve();
fflush(stdout);
#ifdef LOCAL_RELEASE
cerr << clock() - time << endl;
#endif
return 0;
}