QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#709726 | #6513. Expression 3 | MiniLong | TL | 1ms | 11808kb | C++20 | 3.2kb | 2024-11-04 16:28:46 | 2024-11-04 16:28:47 |
Judging History
answer
#include <bits/stdc++.h>
#define _rep(i, x, y) for(int i = x; i <= y; ++i)
#define _req(i, x, y) for(int i = x; i >= y; --i)
#define _rev(i, u) for(int i = head[u]; i; i = e[i].nxt)
#define pb push_back
#define fi first
#define se second
#define mst(f, i) memset(f, i, sizeof f)
using namespace std;
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
typedef long long ll;
typedef pair<int, int> PII;
namespace fastio{
#ifdef ONLINE_JUDGE
char ibuf[1 << 20],*p1 = ibuf, *p2 = ibuf;
#define get() p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++
#else
#define get() getchar()
#endif
template<typename T> inline void read(T &t){
T x = 0, f = 1;
char c = getchar();
while(!isdigit(c)){
if(c == '-') f = -f;
c = getchar();
}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
t = x * f;
}
template<typename T, typename ... Args> inline void read(T &t, Args&... args){
read(t);
read(args...);
}
template<typename T> void write(T t){
if(t < 0) putchar('-'), t = -t;
if(t >= 10) write(t / 10);
putchar(t % 10 + '0');
}
template<typename T, typename ... Args> void write(T t, Args... args){
write(t), putchar(' '), write(args...);
}
template<typename T> void writeln(T t){
write(t);
puts("");
}
template<typename T> void writes(T t){
write(t), putchar(' ');
}
#undef get
};
using namespace fastio;
#define multitest() int T; read(T); _rep(tCase, 1, T)
namespace Calculation{
const ll mod = 998244353;
ll ksm(ll p, ll h){ll base = p % mod, res = 1; while(h){if(h & 1ll) res = res * base % mod; base = base * base % mod, h >>= 1ll;} return res;}
void dec(ll &x, ll y){x = ((x - y) % mod + mod) % mod;}
void add(ll &x, ll y){x = (x + y) % mod;}
void mul(ll &x, ll y){x = x * y % mod;}
ll sub(ll x, ll y){return ((x - y) % mod + mod) % mod;}
ll pls(ll x, ll y){return ((x + y) % mod + mod) % mod;}
ll mult(ll x, ll y){return x * y % mod;}
}
using namespace Calculation;
const int N = 2e5 + 5;
ll n, a[N], fac[N], ifac[N], b[N];
char s[N];
ll f[N][2];
ll C(ll n, ll m){
if(n < m || m < 0) return 0;
if(n == m || !m) return 1;
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
int main(){
read(n);
fac[0] = ifac[0] = fac[1] = ifac[1] = 1;
_rep(i, 2, n) fac[i] = fac[i - 1] * i % mod, ifac[i] = (mod - mod / i) * ifac[mod % i] % mod;
_rep(i, 2, n) ifac[i] = ifac[i - 1] * ifac[i] % mod;
_rep(i, 1, n) read(a[i]); scanf("%s", s + 1);
_rep(i, 1, n - 1) b[i] = s[i] == '+' ? 0 : 1;
ll ans = 0;
_rep(i, 1, n){
f[i][0] = 1, f[i][1] = 0;
_req(j, i - 1, 1){
_rep(k, 0, 1) f[j][k] = (f[j + 1][k ^ b[j]] + f[j + 1][k] * (i - j - 1) % mod) % mod;
}
ll cur = C(n - 1, i - 1) * fac[n - i] % mod;
add(ans, f[1][0] * cur % mod * a[i] % mod + f[1][1] * cur % mod * (mod - a[i]) % mod);
}
writeln(ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 9716kb
input:
4 9 1 4 1 -+-
output:
46
result:
ok 1 number(s): "46"
Test #2:
score: 0
Accepted
time: 0ms
memory: 11808kb
input:
5 1 2 3 4 5 +-+-
output:
998244313
result:
ok 1 number(s): "998244313"
Test #3:
score: -100
Time Limit Exceeded
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...