#728861 (C++17) No.1800 Random XOR

提出ソース
結果

問題	No.1800 Random XOR
ユーザー	bowwowforeach
提出日時	2022-01-07 22:04:20
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	17,192 bytes
コンパイル時間	2,272 ms
コンパイル使用メモリ	207,184 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-11-14 08:48:17
合計ジャッジ時間	2,908 ms
ジャッジサーバーID （参考情報）	judge5 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,820 KB
testcase_03	AC	2 ms 6,820 KB
testcase_04	AC	2 ms 6,816 KB
testcase_05	AC	2 ms 6,820 KB
testcase_06	AC	2 ms 6,816 KB
testcase_07	AC	2 ms 6,820 KB
testcase_08	AC	2 ms 6,820 KB
testcase_09	AC	2 ms 6,816 KB
testcase_10	AC	2 ms 6,816 KB
testcase_11	AC	2 ms 6,816 KB
testcase_12	AC	2 ms 6,816 KB
testcase_13	AC	2 ms 6,820 KB
testcase_14	AC	2 ms 6,820 KB
testcase_15	AC	2 ms 6,816 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;


#define FOR(i, s, e) for (int i = int(s); i < int(e); ++i)
#define RFOR(i, s, e) for (int i = int(e) - 1; i >= int(s); --i)
#define REP(i, n) for (int i = 0, i##_size = int(n); i < i##_size; ++i)
#define RREP(i, n) for (int i = int(n) - 1; i >= 0; --i)
#define ALL(x) (x).begin(),(x).end()

#define rep(i, n) for (int i = 0, i##_size = int(n); i < i##_size; ++i)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()

template <class T> inline void chmin(T& a, T b) { if (b < a) { a = b; } }
template <class T> inline void chmax(T& a, T b) { if (a < b) { a = b; } }
template <class T> inline constexpr T square(T v) { return v * v; }

template <class T, class... Params>
void InstanceRun(Params&&... params) {
	T* m = new T;
	m->Run(forward<Params>(params)...);
}

struct Main;

int main(int argc, const char* argv[]) {
	cin.tie(0);
	ios::sync_with_stdio(0);
	InstanceRun<Main>(argc, argv);
}


using ll = long long;
#define int ll
#define INF INT64_MAX


template <class T>
struct arr : public vector<T> {
	static arr<arr<T>> D2(int y, int x, T value) {
		return arr<arr<T>>(y, arr<T>(x, value));
	}
	static arr<arr<arr<T>>> D3(int z, int y, int x, T value) {
		return arr<arr<arr<T>>>(z, arr<arr<T>>(y, arr<T>(x, value)));
	}

	static arr<T> Iota(int N, int value = 0) {
		auto r = arr<T>(N);
		r.iota(value);
		return r;
	}
	arr() {}
	arr(initializer_list<T> il) : vector<T>(il) {}
	explicit arr(int n) : vector<T>(n) {}
	arr(int n, T v) : vector<T>(n, v) {}
	arr(const arr& r) : vector<T>(r) {}
	arr(arr&& r) : vector<T>(move(r)) {}

	arr& operator = (const arr& r) {
		vector<T>::operator = (r);
		return *this;
	}
	arr& operator = (arr&& r) {
		vector<T>::operator = (move(r));
		return *this;
	}


	T& operator()(int i) { return (*this)[i]; }
	T const& operator()(int i) const { return (*this)[i]; }
	void init(int n, T v = T()) {
		this->assign(n, v);
	}
	int sz() const { return (int)this->size(); }
	void pb(T v) { this->push_back(v); }
	void sort() { std::sort(this->begin(), this->end()); }
	template <class F> void sort(F&& f) { std::sort(this->begin(), this->end(), f); }
	void rsort() { std::sort(this->begin(), this->end(), greater<T>()); }
	void reverse() { std::reverse(this->begin(), this->end()); }
	void unique_erase() { this->erase(std::unique(this->begin(), this->end()), this->end()); }
	bool next_permutation() { return std::next_permutation(this->begin(), this->end()); }
	int lower_bound(T const& v, function<bool(T, T)> p) { return std::lower_bound(this->begin(), this->end(), v, p) - this->begin(); }
	int lower_bound(T const& v) { return std::lower_bound(this->begin(), this->end(), v) - this->begin(); }
	int upper_bound(T const& v, function<bool(T, T)> p) { return std::upper_bound(this->begin(), this->end(), v, p) - this->begin(); }
	int upper_bound(T const& v) { return std::upper_bound(this->begin(), this->end(), v) - this->begin(); }
	void iota(T startValue = 0) { ::iota(this->begin(), this->end(), startValue); }
	void fill(T v) { ::fill(this->begin(), this->end(), v); }

	int find_sorted_nearest(T const& v) {
		int i = this->lower_bound(v);
		if (i >= sz()) {
			--i;
		}
		else if ((*this)[i] != v) {
			int p = i - 1;
			if (p >= 0) {
				int id = abs((*this)[i] - v);
				int pd = abs((*this)[p] - v);
				if (pd < id) {
					i = p;
				}
			}
		}
		return i;
	}

	int find_sorted(T const& v) {
		int i = this->lower_bound(v);
		if (i >= sz()) {
			return -1;
		}
		if ((*this)[i] != v) {
			return -1;
		}
		return i;
	}

	int find(T const& v) const {
		auto it = std::find(this->begin(), this->end(), v);
		if (it == this->end()) {
			return -1;
		}
		return it - this->begin();
	}
	bool is_contains(T const& v) const {
		auto it = std::find(this->begin(), this->end(), v);
		if (it == this->end()) {
			return false;
		}
		return true;
	}

	template <class P>
	void remove_if_erase(P&& predicate) { this->erase(std::remove_if(this->begin(), this->end(), predicate), this->end()); }

	T& emplace_back_ref() {
		this->emplace_back();
		return this->back();
	}

	friend ostream& operator<<(ostream& os, const arr<T>& p) {
		if (p.empty()) {
			return os;
		}
		os << p[0];
		FOR(i, 1, p.size()) {
			os << " " << p[i];
		}
		return os;
	}
};
using ints = arr<int>;


template <class A, class B>
struct pr {
	union {
		A a;
		A key;
		A first;
		A x;
	};
	union {
		B b;
		B value;
		B second;
		B y;
	};

	bool operator == (pr const& r) const { return a == r.a && b == r.b; }
	bool operator != (pr const& r) const { return !((*this) == r); }
	bool operator < (pr const& r) const {
		if (a == r.a) {
			return b < r.b;
		}
		return a < r.a;
	}

	pr& operator += (pr const& v) {
		a += v.a;
		b += v.b;
		return *this;
	}
	pr& operator -= (pr const& v) {
		a -= v.a;
		b -= v.b;
		return *this;
	}
	pr operator + (pr const& v) const { return pr{ a, b } += v; }
	pr operator - (pr const& v) const { return pr{ a, b } -= v; }
	pr operator - () const { return pr{ -a, -b }; }

	template <class C, class D>
	operator pr<C, D>() const {
		return { C(a), D(b) };
	}

	template <class T>
	auto operator * (T const& v) const -> pr<decltype(x * v), decltype(y * v)> {
		return { x * v, y * v };
	}
	template <class T>
	auto operator / (T const& v) const -> pr<decltype(x / v), decltype(y / v)> {
		return { x / v, y / v };
	}

	template <class T>
	pr& operator *= (T const& v) {
		x *= v;
		y *= v;
		return *this;
	}
	template <class T>
	pr& operator /= (T const& v) {
		x /= v;
		y /= v;
		return *this;
	}

	void flip() { swap(x, y); }

	friend istream& operator>>(istream& is, pr& p) {
		is >> p.a >> p.b;
		return is;
	}
	friend ostream& operator<<(ostream& os, pr const& p) {
		os << p.a << " " << p.b;
		return os;
	}
};
using pint = pr<int, int>;
using pdouble = pr<double, double>;

static_assert(is_pod<pint>::value, "not pod");

template <class A, class B, class C>
struct tr {
	union {
		A a;
		A first;
		A x;
	};
	union {
		B b;
		B second;
		B y;
	};
	union {
		C c;
		C third;
		C z;
	};

	bool operator == (tr const& r) const { return a == r.a && b == r.b && c == r.c; }
	bool operator != (tr const& r) const { return !((*this) == r); }
	bool operator < (tr const& r) const {
		if (a == r.a) {
			if (b == r.b) {
				return c < r.c;
			}
			return b < r.b;
		}
		return a < r.a;
	}

	tr operator + (tr v) const { return tr(x, y, z) += v; }
	tr operator - (tr v) const { return tr(x, y, z) -= v; }
	tr operator - () const { return tr{ -x, -y, -z }; }

	tr& operator += (tr v) {
		x += v.x;
		y += v.y;
		z += v.z;
		return *this;
	}
	tr& operator -= (tr v) {
		x -= v.x;
		y -= v.y;
		z -= v.z;
		return *this;
	}

	friend istream& operator>>(istream& is, tr& p) {
		is >> p.a >> p.b >> p.c;
		return is;
	}
	friend ostream& operator<<(ostream& os, tr const& p) {
		os << p.a << " " << p.b << " " << p.c;
		return os;
	}
};

using tint = tr<int, int, int>;
static_assert(is_pod<tint>::value, "not pod");

template <class T>
struct arr2 {
	vector<vector<T>>	m_vec;
	int			m_width;
	int			m_height;

	arr2() : m_width(0), m_height(0) {}
	arr2(int w, int h, T const& value = T()) : m_width(w), m_height(h) {
		m_vec.resize(h, vector<T>(w, value));
	}
	arr2(arr2 const& r) {
		m_vec = r.m_vec;
		m_width = r.m_width;
		m_height = r.m_height;
	}
	arr2(arr2&& r) {
		m_vec = move(r.m_vec);
		m_width = r.m_width;
		m_height = r.m_height;
	}
	arr2& operator=(arr2 const& r) {
		m_vec = r.m_vec;
		m_width = r.m_width;
		m_height = r.m_height;
		return *this;
	}
	arr2& operator=(arr2&& r) {
		m_vec = move(r.m_vec);
		m_width = r.m_width;
		m_height = r.m_height;
		return *this;
	}

	bool operator ==(arr2 const& r) const {
		return m_vec == r.m_vec;
	}

	bool operator <(arr2 const& r) const {
		if (m_width != r.m_width) {
			return m_width < r.m_width;
		}
		if (m_height != r.m_height) {
			return m_height < r.m_height;
		}
		REP(y, m_height) {
			REP(x, m_width) {
				if ((*this)(x, y) != r(x, y)) {
					return (*this)(x, y) < r(x, y);
				}
			}
		}
		return false;
	}

	pint size() const { return pint{ m_width, m_height }; }
	int width() const { return m_width; }
	int height() const { return m_height; }

	void clear() {
		m_vec.clear();
		m_width = 0;
		m_height = 0;
	}

	void init(int w, int h, T const& value = T()) {
		m_vec.clear();
		m_vec.resize(h, vector<T>(w, value));
		m_width = w;
		m_height = h;
	}
	void init(pint size, T const& value = T()) {
		init(size.x, size.y, value);
	}

#if VALIDATION
	void CheckOutOfRange(int x, int y) const {
		if (x < 0 || y < 0 || x >= m_width || y >= m_height) {
			VALIDATE_ABORT();
		}
	}
	void CheckOutOfRange(const pint& p) const {
		if (p.x < 0 || p.y < 0 || p.x >= m_width || p.y >= m_height) {
			VALIDATE_ABORT();
		}
	}
#endif

	T& operator()(int x, int y) {
#if VALIDATION
		CheckOutOfRange(x, y);
#endif
		return m_vec[y][x];
	}
	T const& operator()(int x, int y) const {
#if VALIDATION
		CheckOutOfRange(x, y);
#endif
		return m_vec[y][x];
	}

	T& operator()(pint p) {
#if VALIDATION
		CheckOutOfRange(p);
#endif
		return m_vec[p.y][p.x];
	}
	T const& operator()(pint p) const {
#if VALIDATION
		CheckOutOfRange(p);
#endif
		return m_vec[p.y][p.x];
	}

	T& operator[](pint p) {
#if VALIDATION
		CheckOutOfRange(p);
#endif
		return m_vec[p.y][p.x];
	}
	T const& operator[](pint p) const {
#if VALIDATION
		CheckOutOfRange(p);
#endif
		return m_vec[p.y][p.x];
	}

	vector<T>& operator[](int row) {
#if VALIDATION
		if (row < 0 || row >= m_height) {
			VALIDATE_ABORT();
		}
#endif
		return m_vec[row];
	}
	vector<T> const& operator[](int row) const {
#if VALIDATION
		if (row < 0 || row >= m_height) {
			VALIDATE_ABORT();
		}
#endif
		return m_vec[row];
	}

	bool isIn(int x, int y) const {
		return
			x >= 0 && x < m_width&&
			y >= 0 && y < m_height;
	}
	bool isIn(pint p) const { return isIn(p.x, p.y); }
	bool isOut(int x, int y) const {
		return
			x < 0 || x >= m_width ||
			y < 0 || y >= m_height;
	}
	bool isOut(pint p) const { return isOut(p.x, p.y); }

	void disp(ostream& os, int w = 2) {
		REP(y, m_height) {
			REP(x, m_width) {
				os << setw(w) << (*this)(x, y) << " ";
			}
			os << endl;
		}
		os << endl;
	}
};

template <class K, class V>
struct dic : public map<K, V> {

	bool get(K const& k, V* v) const {
		auto it = this->find(k);
		if (it != this->end()) {
			*v = it->second;
			return true;
		}
		return false;
	}

	typename map<K, V>::const_iterator find_less_than_equal(const K& k) const {
		auto it = this->lower_bound(k);

		if (it == this->end()) {
			if (it == this->begin()) {
				return this->end();
			}
			return prev(it);
		}
		else if (it->first == k) {
			return it;
		}
		else {
			if (it == this->begin()) {
				return this->end();
			}
			return prev(it);
		}
	}

	typename map<K, V>::const_iterator find_greater_than_equal(const K& k) const {
		return this->lower_bound(k);
	}


};

struct PrintStream {
	ostream& os_;
	bool printed_ = false;
	string space_ = " ";

	PrintStream(ostream& os, const string& space = " ") : os_(os), space_(space) {
	}

	template <class T>
	friend PrintStream& operator<<(PrintStream& ps, T&& v) {
		if (ps.printed_) {
			ps.os_ << ps.space_ << v;
		}
		else {
			ps.os_ << v;
			ps.printed_ = true;
		}
		return ps;
	}

	PrintStream& operator <<(PrintStream& (*manip)(PrintStream&)) {
		return (*manip)(*this);
	}
};

PrintStream& endl(PrintStream& ps) {
	ps.os_ << '\n';
	ps.printed_ = false;
	return ps;
}

struct OutputStream {
	ostream& os_;
	OutputStream(ostream& os) : os_(os) {
	}

	template <class T>
	friend OutputStream& operator<<(OutputStream& s, T const& v) {
		s.os_ << v << '\n';
		return s;
	}
};
#include <cstdint>

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using s8 = int8_t;
using s16 = int16_t;
using s32 = int32_t;
using s64 = int64_t;

using ints = arr<int>;
using pint = pr<int, int>;
using pints = arr<pint>;
using tint = tr<int, int, int>;
using tints = arr<tint>;
using int2 = arr2<int>;

const pints around4 = { pint{-1, 0}, pint{0, -1}, pint{1, 0}, pint{0, 1} };


constexpr int gcd(int a, int b) {
	if (a < 0) { a = -a; }
	if (b < 0) { b = -b; }
	if (a == 0) { return b; }
	if (b == 0) { return a; }

	while (int c = a % b) {
		a = b;
		b = c;
	}
	return b;
}

constexpr int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}

int popcount(int v) {
	return bitset<64>(v).count();
}

int64_t msb(int64_t v) {
	if (v == 0) return false;
	v |= (v >> 1);
	v |= (v >> 2);
	v |= (v >> 4);
	v |= (v >> 8);
	v |= (v >> 16);
	v |= (v >> 32);
	return popcount(v) - 1;
}


#ifdef LOCAL_TEST
stringstream inputStream;
stringstream outputStream;
stringstream errorStream;
istream& mis = inputStream;
ostream& mos = outputStream;
ostream& mes = errorStream;
#else
istream& mis = cin;
ostream& mos = cout;
ostream& mes = cerr;
#endif



template <class T>
struct TypeInput;

template <>
struct TypeInput<int> {
	static void input(int& v, istream& is) {
		is >> v;
	}
	static void input(int& v, istream& is, int add) {
		is >> v;
		v += add;
	}
};
template <>
struct TypeInput<double> {
	static void input(int& v, istream& is) {
		is >> v;
	}
};
template <>
struct TypeInput<char> {
	static void input(char& v, istream& is) {
		is >> v;
	}
};
template <>
struct TypeInput<string> {
	static void input(string& v, istream& is) {
		is >> v;
	}
};

template <class A, class B>
struct TypeInput<pr<A, B>> {
	static void input(pr<A, B>& v, istream& is) {
		TypeInput<A>::input(v.a, is);
		TypeInput<B>::input(v.b, is);
	}
	static void input(pr<A, B>& v, istream& is, A&& addA, B&& addB) {
		TypeInput<A>::input(v.a, is, addA);
		TypeInput<B>::input(v.b, is, addB);
	}
};

template <class A, class B, class C>
struct TypeInput<tr<A, B, C>> {
	static void input(tr<A, B, C>& v, istream& is) {
		TypeInput<A>::input(v.a, is);
		TypeInput<B>::input(v.b, is);
		TypeInput<C>::input(v.c, is);
	}
	static void input(tr<A, B, C>& v, istream& is, A&& addA, B&& addB, C&& addC) {
		TypeInput<A>::input(v.a, is, addA);
		TypeInput<B>::input(v.b, is, addB);
		TypeInput<C>::input(v.c, is, addC);
	}
};

template <class T>
struct TypeInput<arr<T>> {
	template <class... ARGS>
	static void input(arr<T>& v, istream& is, int N, ARGS&&... args) {
		v.resize(N);
		REP(i, N) {
			TypeInput<T>::input(v[i], is, forward<ARGS>(args)...);
		}
	}
};

template <class T>
struct TypeInput<arr2<T>> {
	template <class... ARGS>
	static void input(arr2<T>& v, istream& is, int H, int W, ARGS&&... args) {
		v.init(W, H);
		REP(y, H) {
			REP(x, W) {
				TypeInput<T>::input(v(x, y), is, forward<ARGS>(args)...);
			}
		}
	}
};

template <class... ARGS>
struct InputParam {
	tuple<ARGS...> args_;
	InputParam(tuple<ARGS...>&& args) : args_(args) {}

	template <class T, class C = decltype(TypeInput<T>())>
	operator T() const {
		T v;
		apply([&](auto&&... args) { TypeInput<T>::input(v, mis, args...); }, args_);
		return v;
	}
};

struct inputObject {
	template <class T, class C = decltype(TypeInput<T>())>
	operator T() {
		T v;
		TypeInput<T>::input(v, mis);
		return v;
	}

	template <class... T>
	InputParam<T...> operator()(T&&... args) {
		return InputParam<T...>(forward_as_tuple(args...));
	}
};


struct StdIO {
	OutputStream out;
	PrintStream prn;
	inputObject in;

	StdIO() : out(mos), prn(mos) {
		cout << fixed << setprecision(numeric_limits<double>::digits10);
		cerr << fixed << setprecision(numeric_limits<double>::digits10);
	}
};

struct AlgoMain;

#ifdef LOCAL_TEST
#include <AlgoTest.h>
#else
struct Main
{
    void Run(int argc, const char* argv[])
    {
		(void)argc;
		(void)argv;
		InstanceRun<AlgoMain>();
    }
};
#endif

constexpr int MOD = 1000000007;

template <int M>
struct modint {
	int raw;

	modint() { raw = 0; }
	modint(int v) {
		if (v < 0) {
			raw = (v % M) + M;
		}
		else if (v >= M) {
			raw = v % M;
		}
		else {
			raw = v;
		}
	}
	modint operator + (modint v) const { return modint(raw) += v; }
	modint operator - (modint v) const { return modint(raw) -= v; }
	modint operator * (modint v) const { return modint(raw) *= v; }

	modint& operator += (modint v) {
		raw += v.raw;
		if (raw >= M) { raw -= M; }
		return *this;
	}
	modint& operator -= (modint v) {
		raw -= v.raw;
		if (raw < 0) { raw += M; }
		return *this;
	}
	modint& operator *= (modint v) {
		raw = (raw * v.raw) % M;
		return *this;
	}
	modint pow(int n) const {
		return modint::pow(raw, n);
	}
	static modint pow(int a, int n) {
		if (n < 0) {
			abort();
		}

		int r = 1;
		while (n) {
			if (n & 1) {
				r = (r * a) % M;
			}
			a = (a * a) % M;
			n >>= 1;
		}
		return modint(r);
	}

	modint inv() const {
		int a = raw;
		int b = M;
		int u = 1;
		int v = 0;
		while (b) {
			int t = a / b;
			a -= t * b;
			u -= t * v;
			swap(a, b);
			swap(u, v);
		}
		u %= M;
		if (u < 0) {
			u += M;
		}
		return u;
	}

	friend istream& operator>>(istream& is, modint& m) {
		int v;
		is >> v;
		m = modint(v);
		return is;
	}
	friend ostream& operator<<(ostream& os, modint const& m) {
		return os << m.raw;
	}
};
using mint = modint<MOD>;
using mints = arr<mint>;
using mint2 = arr2<mint>;

struct AlgoMain : public StdIO {
	void Run() {
		int N = in;
		int M = in;
		mint inv(2);
		mint ans = (mint(2).pow(M) - 1) * inv.inv();
		out << ans;
	}
};
yukicoder

結果

テストケース

ソースコード
