QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#236029#7559. Bocchi the RockJWRuixiRE 0ms0kbC++208.9kb2023-11-03 15:36:312023-11-03 15:36:33

Judging History

你现在查看的是最新测评结果

  • [2023-11-03 15:36:33]
  • 评测
  • 测评结果：RE
  • 用时：0ms
  • 内存：0kb
查看
  • [2023-11-03 15:36:31]
  • 提交

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!
源文件, 语言: C++20

详细

Test #1:

score: 0
Dangerous Syscalls

input:

2
????

output:

result:
English 繁體中文 简体中文

服务器时间: 2024-12-05 08:10:13 | 开源项目