結果

問題 No.3366 Reversible Tile:Revival
コンテスト
ユーザー cho435
提出日時 2025-11-14 18:55:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 285 ms / 3,000 ms
コード長 3,787 bytes
コンパイル時間 4,664 ms
コンパイル使用メモリ 282,364 KB
実行使用メモリ 22,188 KB
最終ジャッジ日時 2025-11-17 20:46:53
合計ジャッジ時間 14,859 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)

template <class T> bool chmin(T& x, T y) {
	return x > y ? (x = y, true) : false;
}
template <class T> bool chmax(T& x, T y) {
	return x < y ? (x = y, true) : false;
}

struct io_setup {
	io_setup() {
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout << fixed << setprecision(15);
	}
} io_setup;

using mint = atcoder::modint998244353;
using ull = unsigned long long;
constexpr int mod = 998244353;

struct Event {
	ll pos;
	ll type;
	ll idx;
	bool operator<(const Event& e) const {
		if (pos != e.pos) return pos < e.pos;
		return type < e.type;
	}
};

void zobrist_init(vector<ull>& a) {
	mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
	for (int i = 0; i < (int)(a.size()); i++) a[i] = rng();
}
ll naru_solve(ll n, ll m, vector<ll> vl, vector<ll> vr) {
	ll two_pow = 748683265;	 // 4^{-1} mod 998244353
	vector<Event> events;
	for (int i = 0; i < m; i++) {
		// cin >> l >> r;
		// events.push_back({l, 0, i});
		// events.push_back({r + 1, 1, i});
		events.push_back({vl[i] + 1, 0, i});
		events.push_back({vr[i] + 1, 1, i});
		two_pow = (two_pow << 1) % mod;
	}
	vector<ull> zobrist(m + 1);
	zobrist_init(zobrist);
	sort(all(events));

	map<ull, ll> t;
	ll last = 1;
	ull hash = 0;
	for (auto& e : events) {
		ll now = e.pos;
		if (now > last) t[hash] = (t[hash] + (now - last)) % mod;
		hash ^= zobrist[e.idx];
		last = now;
	}
	if (last <= n) t[hash] = (t[hash] + (n - last + 1)) % mod;
	ll n0 = t[0], p = 0;
	for (auto& [h, w] : t) {
		if (h) p = (p + w * (w - 1)) % mod;
	}
	ll ans = ((n + n0) % mod) % mod;
	ans = (ans * ((n + n0) % mod)) % mod;
	ans = (ans + n + p - n0) % mod;
	ans = (ans * two_pow) % mod;
	return ans;
}

ll solve(ll n, ll m, vector<ll> l, vector<ll> r) {
	vector<ll> cv = {0, n};
	rep(i, 0, m) {
		cv.push_back(l[i]);
		cv.push_back(r[i]);
	}
	sort(cv.begin(), cv.end());
	cv.erase(unique(cv.begin(), cv.end()), cv.end());
	int k = cv.size();
	auto get_ith = [&](ll x) {
		return lower_bound(cv.begin(), cv.end(), x) - cv.begin();
	};
	vector<ull> im(k);
	{
		random_device rd;
		mt19937_64 mt(rd());
		rep(i, 0, m) {
			int nl = get_ith(l[i]);
			int nr = get_ith(r[i]);
			ull hs = mt();
			im[nl] ^= hs;
			im[nr] ^= hs;
		}
	}
	map<ull, mint> mp;
	rep(i, 0, k - 1) {
		mp[im[i]] += cv[i + 1] - cv[i];
		im[i + 1] ^= im[i];
	}
	mint ans = 0;
	{
		mint tmp = mp[0] + (n - mp[0]) / 2;
		ans += tmp * tmp;
		mp.erase(0);
	}
	for (auto [hs, ad] : mp) {
		ans += ad * ad / 4;
	}
	ans *= mint(2).pow(m);
	return ans.val();
}

ll greedy(ll n, ll m, vector<ll> l, vector<ll> r) {
	mint ans = 0;
	rep(bit, 0, 1 << m) {
		vector<int> f(n + 1);
		rep(i, 0, m) if ((bit >> i) & 1) {
			f[l[i]] ^= 1;
			f[r[i]] ^= 1;
		}
		mint tmp = 0;
		rep(i, 0, n) {
			if (!f[i]) tmp++;
			f[i + 1] ^= f[i];
		}
		// cout << bitset<3>(bit) << ' ' << tmp.val() << endl;
		// rep(i, 0, n) cout << f[i];
		// cout << endl;
		ans += tmp * tmp;
	}
	return ans.val();
}

void test() {
	int n = 20;
	int m = 10;
	vector<ll> l(m), r(m);
	rep(lp, 0, 1000) {
		rep(i, 0, m) {
			l[i] = rand() % n + 1;
			r[i] = rand() % n + 1;
			if (r[i] < l[i]) swap(l[i], r[i]);
			l[i]--;
		}
		auto a1 = solve(n, m, l, r);
		auto a2 = greedy(n, m, l, r);
		if (a1 != a2) {
			cout << a1 << endl;
			cout << a2 << endl;
			cout << n << ' ' << m << endl;
			rep(i, 0, m) cout << l[i] + 1 << ' ' << r[i] << endl;
			assert(0);
		}
	}
}

int main() {
	// test();
	// return 0;
	ll n, m;
	cin >> n >> m;
	vector<ll> l(m), r(m);
	rep(i, 0, m) cin >> l[i] >> r[i], l[i]--;
	// cout << naru_solve(n, m, l, r) << '\n';
	cout << solve(n, m, l, r) << '\n';
	// cout << greedy(n, m, l, r) << '\n';
}
0