QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#373173 | #6513. Expression 3 | ucup-team1191 | TL | 2690ms | 52972kb | C++20 | 9.8kb | 2024-04-01 05:28:56 | 2024-04-01 05:28:57 |
Judging History
answer
// !!!!!!
// rename to template.cpp instead of main.cpp
#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(a) (a).begin(), (a).end()
using namespace std;
#ifdef ONPC
mt19937 rnd(223);
#else
mt19937 rnd(chrono::high_resolution_clock::now()
.time_since_epoch().count());
#endif
#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)
#ifdef ONPC
#define show(x) cerr << "LINE " << __LINE__ << ": " << #x << "=" << x
#else
#define show(x) 42
#endif
using ll = long long;
using ld = double;
// если модуль подается на вход, убрать все <> и раскомментировать нужные строки
using uint = unsigned int;
using ull = unsigned long long;
template <uint MD> struct ModInt {
using M = ModInt;
// static int MD;
uint v;
ModInt(ll _v = 0) { set_v(uint(_v % MD + MD)); }
M& set_v(uint _v) {
v = (_v < MD) ? _v : _v - MD;
return *this;
}
explicit operator bool() const { return v != 0; }
M operator-() const { return M() - *this; }
M operator+(const M& r) const { return M().set_v(v + r.v); }
M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
M operator*(const M& r) const { return M().set_v(uint((ull)v * r.v % MD)); }
M operator/(const M& r) const { return *this * r.inv(); }
M& operator+=(const M& r) { return *this = *this + r; }
M& operator-=(const M& r) { return *this = *this - r; }
M& operator*=(const M& r) { return *this = *this * r; }
M& operator/=(const M& r) { return *this = *this / r; }
bool operator==(const M& r) const { return v == r.v; }
bool operator!=(const M& r) const { return v != r.v; }
M inv() const;
friend istream& operator>>(istream& is, M& r) { ll x; is >> x; r = M(x); return is; }
friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
template<uint MD>
ModInt<MD> pow(ModInt<MD> x, ll n) {
ModInt<MD> r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
template<uint MD>
ModInt<MD> ModInt<MD>::inv() const { return pow(*this, MD - 2); }
// or copy egcd and {return egcd(MD, v, 1).second;}
// if MD is from input
// this line is necessary, read later as you wish
// int ModInt::MD;
using Mint = ModInt<998244353>;
// using Mint = double;
#define V vector
void nft(bool type, V<Mint>& a) {
Mint G = 3;
int n = int(a.size()), s = 0;
while ((1 << s) < n) s++;
assert(1 << s == n);
static V<Mint> ep, iep;
while (int(ep.size()) <= s) {
ep.push_back(pow(G, Mint(-1).v / (1 << ep.size())));
iep.push_back(ep.back().inv());
}
V<Mint> b(n);
for (int i = 1; i <= s; i++) {
int w = 1 << (s - i);
Mint base = type ? iep[i] : ep[i], now = 1;
for (int y = 0; y < n / 2; y += w) {
for (int x = 0; x < w; x++) {
auto l = a[y << 1 | x];
auto r = now * a[y << 1 | x | w];
b[y | x] = l + r;
b[y | x | n >> 1] = l - r;
}
now *= base;
}
swap(a, b);
}
}
const ll MOD2 = 998244353LL * 998244353;
V<Mint> multiply_nft(const V<Mint>& a, const V<Mint>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
if (min(n, m) <= 50) {
V<ll> ansll(n + m - 1);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
ansll[i + j] += (ll)a[i].v * (ll)b[j].v;
if (ansll[i + j] >= MOD2) ansll[i + j] -= MOD2;
}
vector<Mint> ans(ansll.begin(), ansll.end());
return ans;
}
int lg = 0;
while ((1 << lg) < n + m - 1) lg++;
int z = 1 << lg;
auto a2 = a, b2 = b;
a2.resize(z);
b2.resize(z);
nft(false, a2);
nft(false, b2);
for (int i = 0; i < z; i++) a2[i] *= b2[i];
nft(true, a2);
a2.resize(n + m - 1);
Mint iz = Mint(z).inv();
for (int i = 0; i < n + m - 1; i++) a2[i] *= iz;
return a2;
}
struct poly : vector<Mint> {
poly() {}
poly(const vector<Mint> &a) : vector<Mint>(a) {}
poly(int n) : vector<Mint>(n, 0) {}
template <class It>
poly(It left, It right) : vector<Mint>(left, right) {}
inline void normalize() {
while (size() > 1 && back() == 0) pop_back();
}
inline Mint& operator[](int pos) {
if (pos >= (int)size()) resize(pos + 1);
return vector<Mint>::operator[](pos);
}
inline Mint operator[](int pos) const {
if (pos < (int)size()) return vector<Mint>::operator[](pos);
return 0;
}
inline poly operator+(const poly &b) const {
const poly &a = *this;
poly ans(max((int)a.size(), (int)b.size()));
for (int i = 0; i < ans.size(); i++) ans[i] = a[i] + b[i];
return ans;
}
inline poly operator+=(const poly &p) {
return *this = *this + p;
}
inline poly operator-(const poly &b) const {
const poly &a = *this;
poly ans(max((int)a.size(), (int)b.size()));
for (int i = 0; i < ans.size(); i++) ans[i] = (a[i] - b[i]);
return ans;
}
inline poly operator-=(const poly &p) {
return *this = *this - p;
}
inline poly operator*(Mint d) const {
poly ans = *this;
for (int i = 0; i < (int)ans.size(); i++) ans[i] = ans[i] * d;
return ans;
}
inline poly operator*=(Mint d) {
return *this = *this * d;
}
inline poly operator/(Mint d) const {
d = d.inv();
poly ans = *this;
for (int i = 0; i < (int)ans.size(); i++) ans[i] = ans[i] * d;
return ans;
}
inline poly operator/=(Mint d) {
return *this = *this / d;
}
inline poly operator*(const poly &p) const {
return poly(multiply_nft(*this, p)); // here any multiply with fft should be used
}
inline poly operator*=(const poly &p) {
return *this = *this * p;
}
inline poly cut(int n) const {
poly a = (*this);
a.resize(n);
return a;
}
inline poly invp() const {
poly a(1);
a[0] = 1;
if ((*this)[0] != 1) a[0] = (*this)[0].inv();
for (int n = 1; n < (int)size(); n <<= 1) {
poly ca = cut(n + n);
poly ra = (a * a);
ra.resize(n + n);
ra = (ra * ca);
ra.resize(n + n);
a += a;
a -= ra;
a = a.cut(n + n);
}
a.resize(size());
return a;
}
inline poly rev() const {
poly a = (*this);
reverse(a.begin(), a.end());
return a;
}
inline poly getdiv(poly b) const { // use it only to divide polynomials
poly a = (*this);
a.normalize();
b.normalize();
if (a.size() < b.size()) return poly(1);
int k = (int)a.size() - (int)b.size() + 1;
if (b.back() != 1) b /= b.back();
poly rb = b.rev().cut(k);
return (rb.invp() * a.rev()).cut(k).rev();
}
inline poly operator/(const poly &b) const { // use it only to divide polynomials
return getdiv(b);
}
inline poly operator/=(const poly &b) { // use it only to divide polynomials
return *this = *this / b;
}
inline poly operator%(const poly &b) const { // use it only to divide polynomials
poly a = (*this);
poly d = (a / b);
if (d.size() == 1 && d[0] == 0) return a;
poly r = (a - d * b);
r.normalize();
return r;
}
inline poly operator%=(const poly &b) {
return *this = *this % b;
}
};
const int M = 2e5 + 239;
const int T = (1 << 19) + 239;
int n;
string s;
Mint a[M];
poly mul_minus[T];
poly mul_plus[T];
void build(int i, int l, int r) {
if (r - l == 1) {
if (s[l] == '-') {
mul_minus[i] = poly(vector<Mint>{Mint(-l), Mint(1)});
} else {
mul_minus[i] = poly(vector<Mint>{Mint(1)});
}
mul_plus[i] = poly(vector<Mint>{Mint(-l - 1), Mint(1)});
return;
}
int mid = (l + r) / 2;
build(2 * i + 1, l, mid);
build(2 * i + 2, mid, r);
mul_minus[i] = mul_minus[2 * i + 1] * mul_minus[2 * i + 2];
mul_plus[i] = mul_plus[2 * i + 1] * mul_plus[2 * i + 2];
}
Mint res[M];
void func(const poly& prod, int i, int l, int r) {
if (r - l == 1) {
res[l] = prod[0];
return;
}
int mid = (l + r) / 2;
func(prod % mul_plus[2 * i + 1], 2 * i + 1, l, mid);
func((prod * mul_minus[2 * i + 1]) % mul_plus[2 * i + 2], 2 * i + 2, mid, r);
}
void solve() {
Mint ans;
/*n = 200'000;
ans = 0;
for (int i = 1; i < n; i++) {
a[i - 1] = i;
}
for (int i = 0; i < n - 1; i++) {
s += '-';
}*/
cin >> n;
cin >> ans;
for (int i = 1; i < n; i++) {
cin >> a[i - 1];
}
cin >> s;
n--;
build(0, 0, n);
func(poly(vector<Mint>{Mint(1)}), 0, 0, n);
for (int i = 0; i < n; i++) {
if (i > 0 && s[i - 1] == '-') {
continue;
}
Mint cur = Mint(1);
if (i >= 2) cur = res[i - 2];
if (s[i] == '-') {
cur = -cur;
}
ans += a[i] * cur / res[i];
}
for (int i = 1; i <= n; i++) {
ans *= i;
}
cout << ans << "\n";
}
int main() {
#ifdef ONPC
freopen("input", "r", stdin);
#endif
ios::sync_with_stdio(0); cin.tie(0);
cout << fixed << setprecision(20);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
fflush(stdout);
cerr << "\n\nConsumed " << TIME << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 30188kb
input:
4 9 1 4 1 -+-
output:
46
result:
ok 1 number(s): "46"
Test #2:
score: 0
Accepted
time: 0ms
memory: 30264kb
input:
5 1 2 3 4 5 +-+-
output:
998244313
result:
ok 1 number(s): "998244313"
Test #3:
score: 0
Accepted
time: 2690ms
memory: 52972kb
input:
100000 664815434 205025136 871445392 797947979 379688564 336946672 231295524 401655676 526374414 670533644 156882283 372427821 700299596 166140732 677498490 44858761 185182210 559696133 813911251 842364231 681916958 114039865 222372111 784286397 437994571 152137641 650875922 613727135 209302742 5321...
output:
178167352
result:
ok 1 number(s): "178167352"
Test #4:
score: -100
Time Limit Exceeded
input:
200000 109044620 745578941 396599814 756923982 940933214 875346257 378089839 792684563 491924893 782192923 208569108 421583135 814903710 690275542 15773609 364566266 12890134 661702679 640270667 615999192 13352194 325560419 385152885 265008089 570536451 282429805 331946208 255056541 813809151 150995...