WA 46pts求调
查看原帖
WA 46pts求调
716260
SegmentTree_楼主2025/8/2 09:05
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define ui unsigned int
#define i128 __int128
#define lid (id << 1)
#define rid (id << 1 | 1)
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int N = 5e5+5;
#ifdef ONLINE_JUDGE
#define cin IO::InputHelper::get_instance()
#define cout IO::OutputHelper::get_instance()
#define INPUT_FILE ""
#define OUTPUT_FILE ""
namespace IO {
	using size_type = size_t;
	static constexpr size_type INPUT_BUFFER_SIZE = 1 << 16, OUTPUT_BUFFER_SIZE = 1 << 16, MAX_INTEGER_SIZE = 20, MAX_FLOAT_SIZE = 50;static constexpr char input_file[] = INPUT_FILE, output_file[] = OUTPUT_FILE;
	struct InputHelper {
		FILE *m_file_ptr;char m_buf[INPUT_BUFFER_SIZE], *m_end, *m_cursor;bool m_ok;
		InputHelper &set_bad() { return m_ok = false, *this; }
		template <size_type BlockSize>
		void _reserve() {size_type a = m_end - m_cursor;if (a >= BlockSize) return;memmove(m_buf, m_cursor, a), m_cursor = m_buf;size_type b = a + fread(m_buf + a, 1, INPUT_BUFFER_SIZE - a, m_file_ptr);if (b < INPUT_BUFFER_SIZE) m_end = m_buf + b, *m_end = EOF;}
		template <typename Tp, typename BinaryOperation>
		InputHelper &fill_integer(Tp &ret, BinaryOperation op) {if (!isdigit(*m_cursor)) return set_bad();ret = op(Tp(0), *m_cursor - '0');size_type len = 1;while (isdigit(*(m_cursor + len))) ret = op(ret * 10, *(m_cursor + len++) - '0');m_cursor += len;return *this;}
		explicit InputHelper(const char *inputFileName) : m_ok(true), m_cursor(m_buf + INPUT_BUFFER_SIZE), m_end(m_buf + INPUT_BUFFER_SIZE) { m_file_ptr = *inputFileName ? fopen(inputFileName, "rt") : stdin; }
		~InputHelper() { fclose(m_file_ptr); }
		static InputHelper &get_instance() {static InputHelper s_obj(input_file);return s_obj;}
		static bool is_blank(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\r'; }static bool is_endline(char c) { return c == '\n' || c == EOF; }
		const char &getchar_checked() {_reserve<1>();return *m_cursor;}const char &getchar_unchecked() const { return *m_cursor; }
		void next() { ++m_cursor; }
		template <typename Tp, typename std::enable_if<std::is_signed<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
		InputHelper &operator>>(Tp &num) {while (is_blank(getchar_checked())) next();_reserve<MAX_INTEGER_SIZE>();if (getchar_unchecked() != '-') return fill_integer(num, std::plus<Tp>());next();return fill_integer(num, std::minus<Tp>());}
		template <typename Tp, typename std::enable_if<std::is_unsigned<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
		InputHelper &operator>>(Tp &num) {while (is_blank(getchar_checked())) next();_reserve<MAX_INTEGER_SIZE>();return fill_integer(num, std::plus<Tp>());}
		template <typename Tp, typename std::enable_if<std::is_floating_point<Tp>::value>::type * = nullptr>
		InputHelper &operator>>(Tp &num) {
			bool neg = false, integer = false, decimal = false;while (is_blank(getchar_checked())) next();_reserve<MAX_FLOAT_SIZE>();
			if (getchar_unchecked() == '-') {neg = true;next();}if (!isdigit(getchar_unchecked()) && getchar_unchecked() != '.') return set_bad();
			if (isdigit(getchar_unchecked())) {integer = true;num = getchar_unchecked() - '0';while (next(), isdigit(getchar_unchecked())) num = num * 10 + (getchar_unchecked() - '0');}
			if (getchar_unchecked() == '.') if (next(), isdigit(getchar_unchecked())) {if (!integer) num = 0;decimal = true;Tp unit = 0.1;num += unit * (getchar_unchecked() - '0');while (next(), isdigit(getchar_unchecked())) num += (unit *= 0.1) * (getchar_unchecked() - '0');}
			if (!integer && !decimal) return set_bad();if (neg) num = -num;return *this;
		}
		InputHelper &operator>>(char &c) {while (is_blank(getchar_checked())) next();if (getchar_checked() == EOF) return set_bad();c = getchar_checked(), next();return *this;}
		InputHelper &operator>>(std::string &s) {while (is_blank(getchar_checked())) next();if (getchar_checked() == EOF) return set_bad();s.clear();do {s += getchar_checked();next();} while (!is_blank(getchar_checked()) && getchar_unchecked() != EOF);return *this;}
		explicit operator bool() { return m_ok; }
	};
	struct OutputHelper {
		FILE *m_file_ptr = nullptr;char m_buf[OUTPUT_BUFFER_SIZE], *m_end, *m_cursor;char m_temp_buf[MAX_FLOAT_SIZE], *m_temp_buf_cursor, *m_temp_buf_dot;uint64_t m_float_reserve, m_float_ratio;
		void _write() { fwrite(m_buf, 1, m_cursor - m_buf, m_file_ptr), m_cursor = m_buf; }
		template <size_type BlockSize> void _reserve() {size_type a = m_end - m_cursor;if (a >= BlockSize) return;_write();}
		OutputHelper(const char *outputFileName, size_type prec = 6) : m_cursor(m_buf), m_end(m_buf + OUTPUT_BUFFER_SIZE), m_temp_buf_cursor(m_temp_buf) { m_file_ptr = *outputFileName ? fopen(outputFileName, "wt") : stdout, precision(prec); }
		static OutputHelper &get_instance() {static OutputHelper s_obj(output_file);return s_obj;}
		~OutputHelper() { flush(), fclose(m_file_ptr); }
		void precision(size_type prec) { m_float_reserve = prec, m_float_ratio = uint64_t(std::pow(10, prec)), m_temp_buf_dot = m_temp_buf + prec; }
		OutputHelper &flush() { return _write(), fflush(m_file_ptr), *this; }
		void putchar(const char &c) {if (m_cursor == m_end) _write();*m_cursor++ = c;}
		template <typename Tp, typename std::enable_if<std::is_signed<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
		OutputHelper &operator<<(Tp ret) {_reserve<MAX_INTEGER_SIZE>();size_type len = 0;if (ret >= 0) do *(m_cursor + len++) = '0' + ret % 10, ret /= 10;while (ret);else {putchar('-');do *(m_cursor + len++) = '0' - ret % 10, ret /= 10;while (ret);}for (size_type i = 0, j = len - 1; i < j;) std::swap(*(m_cursor + i++), *(m_cursor + j--));m_cursor += len;return *this;}
		template <typename Tp, typename std::enable_if<std::is_unsigned<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
		OutputHelper &operator<<(Tp ret) {_reserve<MAX_INTEGER_SIZE>();size_type len = 0;do *(m_cursor + len++) = '0' + ret % 10, ret /= 10;while (ret);for (size_type i = 0, j = len - 1; i < j;) std::swap(*(m_cursor + i++), *(m_cursor + j--));m_cursor += len;return *this;}
		template <typename Tp, typename std::enable_if<std::is_floating_point<Tp>::value>::type * = nullptr>
		OutputHelper &operator<<(Tp ret) {
			if (ret < 0) {putchar('-');return *this << -ret;}ret *= m_float_ratio;uint64_t integer = ret;if (ret - integer >= 0.4999999999) integer++;do {*m_temp_buf_cursor++ = '0' + integer % 10;integer /= 10;} while (integer);
			if (m_temp_buf_cursor > m_temp_buf_dot) {do putchar(*--m_temp_buf_cursor);while (m_temp_buf_cursor > m_temp_buf_dot);putchar('.');}else {putchar('0'), putchar('.');for (size_type i = m_temp_buf_dot - m_temp_buf_cursor; i--;) putchar('0');}
			do putchar(*--m_temp_buf_cursor);while (m_temp_buf_cursor > m_temp_buf);
			return *this;
		}
		OutputHelper &operator<<(const char &ret) {putchar(ret);return *this;}
		OutputHelper &operator<<(const char *ret) {while (*ret) putchar(*ret++);return *this;}
		OutputHelper &operator<<(const std::string &ret) { return *this << ret.data(); }
	};
	InputHelper &getline(InputHelper &ih, std::string &line) {line.clear();if (ih.getchar_checked() == EOF) return ih.set_bad();while (!InputHelper::is_endline(ih.getchar_checked())) line += ih.getchar_unchecked(), ih.next();if (ih.getchar_unchecked() != EOF) ih.next();return ih;}
}using IO::getline;
#endif
#if __cpp_constexpr >= 201304L
#define CONSTEXPR14 constexpr 
#else
#define CONSTEXPR14 
#endif
template <uint32_t P>
struct ModInt32 {
	using mint = ModInt32<P>;
	using mod_type = uint32_t;
	mod_type m_val;
	static constexpr mod_type _reduce_norm(int32_t x) { return x < 0 ? x + mod() : x; }
	static constexpr mod_type _mul(mod_type a, mod_type b) { return uint64_t(a) * b % mod(); }
	constexpr ModInt32() : m_val(0) {}
	template <typename Tp, typename std::enable_if<std::is_signed<Tp>::value>::type * = nullptr>
	constexpr ModInt32(Tp val) : m_val(_reduce_norm(val % int32_t(mod()))) {}
	template <typename Tp, typename std::enable_if<std::is_unsigned<Tp>::value>::type * = nullptr>
	constexpr ModInt32(Tp val) : m_val(val % mod()) {}
	static CONSTEXPR14 mint raw(mod_type val) {mint res{};res.m_val = val;return res;}
	static constexpr mod_type mod() { return P; }
	constexpr mod_type val() const { return m_val; }
	CONSTEXPR14 mint pow(uint64_t n) const {mod_type res = 1, b = m_val;while (n) {if (n & 1) res = _mul(res, b);b = _mul(b, b), n >>= 1;}return raw(res);}
	CONSTEXPR14 mint inv() const { return pow(mod() - 2); }
	CONSTEXPR14 mint &operator++() {if (++m_val == mod()) m_val = 0;return *this;}
	CONSTEXPR14 mint &operator--() {if (!m_val) m_val = mod();m_val--;return *this;}
	CONSTEXPR14 mint operator++(int) {mint old(*this);++*this;return old;}
	CONSTEXPR14 mint operator--(int) {mint old(*this);--*this;return old;}
	CONSTEXPR14 mint &operator+=(const mint &rhs) {m_val += rhs.m_val;if (m_val >= mod()) m_val -= mod();return *this;}
	CONSTEXPR14 mint &operator-=(const mint &rhs) {m_val += mod() - rhs.m_val;if (m_val >= mod()) m_val -= mod();return *this;}
	CONSTEXPR14 mint &operator*=(const mint &rhs) {m_val = _mul(m_val, rhs.m_val);return *this;}
	constexpr mint operator+() const { return *this; }
	constexpr mint operator-() const { return raw(m_val ? mod() - m_val : 0); }
	constexpr bool operator==(const mint &rhs) const { return m_val == rhs.m_val; }
	constexpr bool operator!=(const mint &rhs) const { return m_val != rhs.m_val; }
	constexpr bool operator<(const mint &rhs) const { return m_val < rhs.m_val; }
	constexpr bool operator>(const mint &rhs) const { return m_val > rhs.m_val; }
	constexpr bool operator<=(const mint &rhs) const { return m_val <= rhs.m_val; }
	constexpr bool operator>=(const mint &rhs) const { return m_val <= rhs.m_val; }
	template <typename Tp>
	constexpr explicit operator Tp() const { return Tp(m_val); }
	friend CONSTEXPR14 mint operator+(const mint &a, const mint &b) { return mint(a) += b; }
	friend CONSTEXPR14 mint operator-(const mint &a, const mint &b) { return mint(a) -= b; }
	friend CONSTEXPR14 mint operator*(const mint &a, const mint &b) { return mint(a) *= b; }
};
template <typename Istream, uint32_t P>
Istream &operator>>(Istream &is, ModInt32<P> &x) { return is >> x.m_val; }
template <typename Ostream, uint32_t P>
Ostream &operator<<(Ostream &os, const ModInt32<P> &x) { return os << x.val(); }
random_device seed;
mt19937 rnd(seed());
mt19937_64 rnd_64(seed());
/*
hashmod:
5011514792945820589
6021372989429639251
604657124278435993
*/
namespace tianyu{
	struct PAM{
		string s;
		int len[N], fail[N], tr[N][26], cnt[N], tot;
		int getfail(int x, int i){
			while (i - len[x] - 1 < 0 || s[i - len[x] - 1] != s[i]) x = fail[x];
			return x;
		}
		void build(){
			len[1] = -1, tot = 1, fail[0] = 1;
			int cur = 0;
			for (int i = 0;i < s.size();i++){
				int a = s[i] - 'A', pos = getfail(cur, i);
				if (!tr[pos][a]){
					fail[++tot] = tr[getfail(fail[pos], i)][a];
					tr[pos][a] = tot;
					len[tot] = len[pos] + 2;
				}
				cur = tr[pos][a];
				++cnt[cur];
			}
			for (int i = tot;i > 1;i--) cnt[fail[i]] += cnt[i];
		}
	}a, b;
	ll ans = 0;
	void dfs(int x, int y){
		if (x > 1 && y > 1) ans += 1ll * a.cnt[x] * b.cnt[y];
		for (int i = 0;i < 26;i++){
			if (a.tr[x][i] && b.tr[x][i]) dfs(a.tr[x][i], b.tr[x][i]);
		}
	}
	void awa(){
		cin >> a.s >> b.s;
		a.build(), b.build();
		dfs(0, 0);
		dfs(1, 1);
		cout << ans;
	}
}
signed main(){
	int T = 1;
	while (T--) tianyu::awa();
	return 0;
}
2025/8/2 09:05
加载中...