QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #236029 | #7559. Bocchi the Rock | JWRuixi | RE | 0ms | 0kb | C++20 | 8.9kb | 2023-11-03 15:36:31 | 2023-11-03 15:36:33 |
answer
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#define LL long long
#define eb emplace_back
#define FIO(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
using namespace std;
namespace Math {
using ui = unsigned;
using uLL = unsigned long long;
using u128 = __uint128_t;
inline int inv_gcd (int a, int b) {
int __m = b;
int x = 0, y = 1, c = 0;
for (; a; swap(a, b -= a * c)) c = b / a, swap(y, x -= y * c);
assert(b == 1);
return x < 0 ? x + __m : x;
}
struct barret {
ui m;
uLL R;
explicit barret (ui _m) : m(_m), R((uLL)(-1) / _m + 1) {}
ui mod () const { return m; }
ui mul (ui a, ui b) const {
uLL z = a * b;
uLL x = (uLL)(((u128)(z) * R) >> 64);
uLL y = x * m;
return z - y + (z < y ? m : 0);
}
};
template<int m>
struct static_modint {
static_assert(m >= 1,"what are you doing?");
using mint = static_modint;
private:
ui _v;
static constexpr ui umod () { return m; }
public:
static_modint () : _v(0) {}
template<typename T, enable_if_t<is_signed<T>::value>* = nullptr>
static_modint (T v) { v %= umod(); _v = (ui)(v < 0 ? v + umod() : v); }
template<typename T, enable_if_t<is_unsigned<T>::value>* = nullptr>
static_modint (T v) { _v = (ui)(v % umod()); }
ui val () const { return _v; }
mint& operator ++ () {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator -- () {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator ++ (int) {
mint r = *this;
++(*this);
return r;
}
mint operator -- (int) {
mint r = *this;
--(*this);
return r;
}
mint& operator += (const mint &rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator -= (const mint &rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint& operator *= (const mint &rhs) {
uLL z = (uLL)_v * rhs._v % umod();
_v = (ui)z;
return *this;
}
mint& operator /= (const mint &rhs) {
(*this) *= rhs.inv();
return *this;
}
mint operator + () const {
return *this;
}
mint operator - () const {
return mint() - *this;
}
friend mint operator + (const mint &lhs, const mint &rhs) {
return mint(lhs) += rhs;
}
friend mint operator - (const mint &lhs, const mint &rhs) {
return mint(lhs) -= rhs;
}
friend mint operator * (const mint &lhs, const mint &rhs) {
return mint(lhs) *= rhs;
}
friend mint operator / (const mint &lhs, const mint &rhs) {
return mint(lhs) /= rhs;
}
friend bool operator == (const mint &lhs, const mint &rhs) {
return lhs._v == rhs._v;
}
friend bool operator != (const mint &lhs, const mint &rhs) {
return lhs._v != rhs._v;
}
mint inv () const {
return inv_gcd(_v, m);
}
template<typename T>
mint pow (T k) const {
mint r = 1, b = *this;
for (; k; k >>= 1, b = b * b) if (k & 1) r = r * b;
return r;
}
};
template<int id>
struct dynamic_modint {
using mint = dynamic_modint;
private:
ui _v;
static barret bt;
static ui umod () { return bt.mod(); }
public:
static int mod () { return (int)bt.mod(); }
static void set_mod (int m) {
assert(1 <= m);
bt = barret(m);
}
dynamic_modint () : _v(0) {}
template<class T, enable_if_t<is_signed<T>::value>* = nullptr>
dynamic_modint (T v) { v %= umod(); _v = (ui)(v < 0 ? v + umod() : v); }
template<class T, enable_if_t<is_unsigned<T>::value>* = nullptr>
dynamic_modint (T v) { _v = (ui)(v % umod()); }
ui val () const { return _v; }
mint& operator ++ () {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator -- () {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator ++ (int) {
mint r = *this;
++(*this);
return r;
}
mint operator -- (int) {
mint r = *this;
--(*this);
return r;
}
mint& operator += (const mint &rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator -= (const mint &rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint& operator *= (const mint &rhs) {
uLL z = (uLL)_v * rhs._v % umod();
_v = (ui)z;
return *this;
}
mint& operator /= (const mint &rhs) {
(*this) *= rhs.inv();
return *this;
}
mint operator + () const {
return *this;
}
mint operator - () const {
return mint() - *this;
}
friend mint operator + (const mint &lhs, const mint &rhs) {
return mint(lhs) += rhs;
}
friend mint operator - (const mint &lhs, const mint &rhs) {
return mint(lhs) -= rhs;
}
friend mint operator * (const mint &lhs, const mint &rhs) {
return mint(lhs) *= rhs;
}
friend mint operator / (const mint &lhs, const mint &rhs) {
return mint(lhs) /= rhs;
}
friend bool operator == (const mint &lhs, const mint &rhs) {
return lhs._v == rhs._v;
}
friend bool operator != (const mint &lhs, const mint &rhs) {
return lhs._v != rhs._v;
}
ui inv () const {
return inv_gcd(_v, mod());
}
template<typename T>
mint pow (T k) const {
mint r = 1, b = *this;
for (; k; k >>= 1, b = b * b) if (k & 1) r = r * b;
return r;
}
};
template<int id> barret dynamic_modint<id>::bt(998244353);
}
using mint = Math::static_modint<998244353>;
constexpr int N = 5e4 + 7, mod = 998244353;
int n, m, a[N << 1];
char s[N << 1];
mint f[2][N][2][2];
#define Do(o, p, q) \
f[o][1][p][0] += f[!o][1][p][0], \
f[o][2][p][q] += f[!o][1][!p][0]
#define DO(o, j, p, q) \
f[o][j][p][0] += f[!o][j][p][0], \
f[o][j][p][1] += f[!o][j][p][1], \
f[o][j + 1][p][q] += f[!o][j][!p][!q], \
f[o][j - 1][p][!q] += f[!o][j][!p][q]
int main() {
FIO("1");
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> s;
m = n << 1;
for (int i = 0; i < m; ++i) {
a[i] = (s[i] == '?') ? 2 : (s[i] == "YR"[i & 1]);
}
if (a[0] != 0) {
f[0][1][1][0] = 1;
}
if (a[0] != 1) {
f[0][1][0][0] = 1;
}
for (int i = 1; i < n; ++i) {
int o = i & 1, u = (i << 1) - 1;
for (int j = 1; j <= i + 1; ++j) {
f[o][j][0][0] = mint();
f[o][j][0][1] = mint();
f[o][j][1][0] = mint();
f[o][j][1][1] = mint();
}
bool f0 = a[u] != 0, f1 = a[u] != 1;
if (a[u + 1] != 0) {
if (f0) Do(o, 1, 1);
if (f1) Do(o, 1, 0);
for (int j = 2; j <= i; ++j) {
if (f0) DO(o, j, 1, 1);
if (f1) DO(o, j, 1, 0);
}
}
if (a[u + 1] != 1) {
if (f0) Do(o, 0, 1);
if (f1) Do(o, 0, 0);
for (int j = 2; j <= i; ++j) {
if (f0) DO(o, j, 0, 1);
if (f1) DO(o, j, 0, 0);
}
}
f[o][1][0][0] += f[o][1][0][1];
f[o][1][1][0] += f[o][1][1][1];
f[o][1][0][1] = f[o][1][1][1] = mint();
}
int o = ((n - 1) & 1);
mint as = f[o][1][0][0] + f[o][1][1][0];
if (a[m - 1] == 2) as *= 2;
if (a[m - 1] != 0) as += (f[o][2][1][1] + f[o][2][0][1]);
if (a[m - 1] != 1) as += (f[o][2][1][0] + f[o][2][0][0]);
cout << as.val();
}
// I love WHQ!
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Dangerous Syscalls
input:
2 ????