C++14用mod_int

C++14用mod_intです。勝手にmodを取ります。
型名はmintです。

using mint = mint_base<1000000007>;

の1000000007がとるmodになります。
+-*/やインクリメント,デクリメントが出来ます。
~で逆元を取れますが、そのままでも割り算が使えます。(どちらもlogMOD)
ストリーム演算子があるので、>>や<<で入出力が出来ます。
繰り返し二条法(ipow),組み合わせ(fact_set),階乗(combination)も一緒に入ってます。
ユーザー定義リテラル_miがあるので、mint(1)の代わりに1_miと出来ます。

#include <algorithm>
#include <utility>
#include <type_traits>
#include <cstdint>
template<typename Arithmetic, typename Integral>
std::enable_if_t< std::is_unsigned<Integral>::value, Arithmetic>
ipow(Arithmetic bace, Integral n)
{
	//繰り返し二条法
	auto res = (Arithmetic)(1);
	while (n > 0) {
		if (n & 1) res *= bace;
		bace *= bace;
		n >>= 1;
	}
	return res;
}
template <uint64_t MOD> class mint_base;
//mint_base_base型用の累乗関数
template <uint64_t MOD> constexpr mint_base<MOD> m_pow(mint_base<MOD> x, uint64_t n)noexcept;
//mod計算を自動で行う整数テンプレートクラス
template <uint64_t MOD_ = 1000000007>
class mint_base
{
public:
	static constexpr auto MOD = MOD_;
	static_assert(!(MOD <= 2), "MOD cannot be below 2.");
	static_assert(MOD <= (0xFFFFFFFFFFFFFFFF / 2), "MOD is too big");//加算してオーバーフローしない
	static_assert(MOD <= 0xFFFFFFFF, "MOD is too big");//乗算してオーバーフローしない
	constexpr mint_base<MOD> operator+(const mint_base<MOD> &other)const noexcept
	{
		auto v = *this;
		return v += other;
	}
	constexpr mint_base<MOD> operator-(const mint_base<MOD> &other)const noexcept
	{
		auto v = *this;
		return v -= other;
	}
	constexpr mint_base<MOD> operator*(const mint_base<MOD> &other)const noexcept
	{
		auto v = *this;
		return v *= other;
	}
	constexpr auto operator/(const mint_base<MOD> &other)const noexcept
	{
		auto v = *this;
		return v /= other;
	}
	constexpr mint_base<MOD>& operator+=(const mint_base<MOD> &other) noexcept
	{
		a += other.a;
		if (MOD <= a) { a -= MOD; };
		return *this;
	}
	constexpr mint_base<MOD>& operator-=(const mint_base<MOD> &other) noexcept
	{
		if (a >= other.a) {
			a -= other.a;
		}
		else {
			a = (a + MOD) - other.a;
		}
		return *this;
	}
	constexpr mint_base<MOD>& operator*=(const mint_base<MOD> &other) noexcept
	{
#if 1
		a *= other.a;
		a %= MOD;
#else
		//MOD <= (MAXUINT64 / 2)条件下
		uint64_t b = other.a, v = 0;
		while (b > 0) {
			if (b & 1) {
				v += a;
				if (v >= MOD)v -= MOD;
			}
			a += a;
			if (MOD <= a)a -= MOD;
			b >>= 1;
		}
		a = v;
#endif
		return *this;
	}
	constexpr mint_base<MOD>& operator/=(const mint_base<MOD> &other) noexcept
	{
		return *this *= ~other;
	}
	constexpr mint_base<MOD> operator+()const noexcept { return *this; }
	constexpr mint_base<MOD> operator-()const noexcept
	{
		return{ MOD - a, mod_value_tag{} };
	}
	constexpr mint_base<MOD>& operator++() noexcept
	{
		if (MOD <= ++a) { a = 0; };
		return *this;
	}
	constexpr mint_base<MOD>& operator--() noexcept
	{
		if (a <= 0) { a = MOD; };
		--a;
		return *this;
	}
	constexpr mint_base<MOD> operator++(int) noexcept
	{
		auto tmp = *this;
		++*this;
		return tmp;
	}
	constexpr mint_base<MOD> operator--(int) noexcept
	{
		auto tmp = *this;
		--*this;
		return tmp;
	}
	constexpr mint_base<MOD> operator~()const noexcept
	{
		return ipow(*this, e_phi - 1);
	}
	constexpr mint_base<MOD>& operator=(const mint_base<MOD> &other) noexcept
	{
		a = other.a;
		return *this;
	}
	constexpr explicit operator uint64_t()const noexcept
	{
		return a;
	}
	constexpr explicit operator unsigned()const noexcept
	{
		return (unsigned)a;
	}
	static constexpr uint64_t getmod() noexcept
	{
		return MOD;
	}
	constexpr mint_base(uint64_t a_) noexcept :a(a_ % MOD) {}
	constexpr mint_base()noexcept : a(0) {}
	struct mod_value_tag {};
	constexpr mint_base(uint64_t a_, mod_value_tag) :a(a_) {}
private:
	static constexpr uint64_t get_e_phi()noexcept {
		//オイラー値の導出
		uint64_t temp = MOD;
		uint64_t m_ = MOD;
		for (uint64_t i = 2; i * i <= m_; ++i)
		{
			if (m_ % i == 0)
			{
				temp = temp / i * (i - 1);
				for (; m_ % i == 0; m_ /= i);
			}
		}
		if (m_ != 1)temp = temp / m_ * (m_ - 1);
		return temp;
	}
	static constexpr uint64_t e_phi = get_e_phi();//オイラー値
	uint64_t a;
};
//mint_base型用の累乗関数
template<uint64_t MOD>constexpr mint_base<MOD> m_pow(mint_base<MOD> x, uint64_t n)noexcept
{
	mint_base<MOD> res = 1;
	while (n > 0)
	{
		if (n & 1)res *= x;
		x *= x;
		n >>= 1;
	}
	return res;
}
//mint_baseの階乗計算
//O(x)時間が必要のため、fact_set関数を推奨する。
template<uint64_t MOD>constexpr mint_base<MOD> fact(mint_base<MOD> x)noexcept
{
	mint_base<MOD> res(1);
	for (uint64_t i = 1; i <= (uint64_t)x; ++i)
	{
		res *= i;
	}
	return res;
}
//mint_baseの階乗計算
//0からxまでの階乗を返す
//O(x)時間が必要
template<uint64_t MOD>std::vector<mint_base<MOD>> fact_set(mint_base<MOD> x = mint_base<MOD>(-1))
{
	mint_base<MOD> res(1);
	std::vector<mint_base<MOD>> set((uint64_t)(x)+1);
	set[0] = 1;
	for (uint64_t i = 1; i <= (uint64_t)x; ++i)
	{
		res *= i;
		set[i] = res;
	}
	return res;
}
//mint_base型のstreamへの出力
template<uint64_t MOD> std::ostream& operator<<(std::ostream& os, mint_base<MOD> i)
{
	os << (uint64_t)i;
	return os;
}
//mint_base型のstreamからの入力
template<uint64_t MOD> std::istream& operator >> (std::istream& is, mint_base<MOD>& i)
{
	uint64_t tmp;
	is >> tmp;
	i = tmp;
	return is;
}
typedef mint_base<1000000007> mint;
namespace mint_literal {
	constexpr mint operator""_mi(unsigned long long x)noexcept {
		return mint(x);
	}
}
using namespace mint_literal;
//mint_baseの階乗計算
//0からxまでの階乗を返す
//O(N)
template<int32_t X, uint64_t MOD = mint::MOD>
/*constexpr*/ std::array<mint_base<MOD>, X + 1> fact_set_c()
{
	mint_base<MOD> res(1);
	std::array<mint_base<MOD>, X + 1> set;
	set[0] = 1;
	for (int32_t i = 1; i <= X; ++i)
	{
		res *= i;
		set[i] = res;
	}
	return set;
}
template<typename RET = mint, typename Integral>
RET combination(Integral all, Integral get)
{
	assert(all >= get);
	get = std::min(all - get, get);
#if 1
	//時間計算量O(logMOD)
	static const auto fact_v = fact_set_c<100001>();
	return fact_v[all] / (fact_v[get] * fact_v[all - get]);
#elif 0
	//時間計算量O(1)
	//空間計算量、初期化時間計算量O(N^2)
	constexpr int32_t ALL_MAX = 10'000;
	static std::vector<RET> DP_comb[ALL_MAX + 1];
	if (!DP_comb[all].empty())
	{
		return DP_comb[all][get];
	}

	if (DP_comb[0].empty())
	{
		DP_comb[0].resize(1);
		DP_comb[0][0] = (RET)1;
		DP_comb[1].resize(1);
		DP_comb[1][0] = (RET)1;
	}
	for (int32_t i = 2; i <= all; i++)
	{
		if (DP_comb[i].empty())
		{
			int32_t size = i / 2 + 1;
			DP_comb[i].resize(size);
			DP_comb[i][0] = (RET)1;
			for (int32_t j = 1; j < size - 1; j++)
			{
				DP_comb[i][j] = DP_comb[i - 1][j - 1] + DP_comb[i - 1][j];
			}
			DP_comb[i][size - 1] = DP_comb[i - 1][size - 2] + DP_comb[i - 1][(i & 1) ? (size - 1) : (size - 2)];
		}
	}
	return DP_comb[all][get];
#else
	//時間計算量O(get + logMOD)
	RET ret = (RET)1;
	for (Integral i = 1; i <= get; ++i)
	{
		ret *= all + 1 - i;
		ret /= i;
	}
	return ret;
#endif
}

N次元配列を同じ値で埋めるテンプレ

N次元配列を同じ値で埋めるテンプレを置いておきます

template<typename T>
void fill_all(T& arr, const T& v) {
	arr = v;
}
template<typename ARR, typename U>
void fill_all(ARR& arr, const U& v) {
	for (auto& i : arr) { fill_all(i, v); }
}

使用例

int dp[1000][1000];
fill_all(dp,-1);//dpの全ての要素に-1を代入

JOI2012予選4「暑い日々」のオーバーキル考察

JOI 2012-2013 予選 問題4
これの解答に触れられているものの解説されていない想定オーバーキル考察です。

続きを読む

幅優先探索の一般的な罠

幅優先探索でTLEする一般的な罠の解説です。
こういうグリッドを幅優先する問題で起こりやすいですね。
C: 幅優先探索 - AtCoder Beginner Contest 007 | AtCoder


簡単のためこのような迷路を考えます。(#壁、.通行可)

/abcdef
1######
2####G#
3###..#
4##...#
5#...##
6#S.###
7######

この迷路の幅優先探索は本来こうあるべきです

{(b,6)}
->{(b,5),(c,6)}
->{(c,5)}
->{(c,4),(d,5)}
->{(d,4)}
->{(e,4),(d,3)}

ところが、このようなコードを書くと

struct Point {
	int y, x;
};
char map[100][100];             //HW '.'通行可、'#'通行不可
bool visited[100][100] = {};    //HW 確認したらtrueに
int  dist[100][100];            //HW Sからの距離

que.push(S);
dist[S.y][S.x] = 0; visited[S.y][S.x] = true;
while (!que.empty()) {
	Point now = que.front(); que.pop();
	visited[now.y][now.x] = true;
	const int diff[] = { 1,0,-1,0,1 };
	for (int i = 0; i < 4; ++i) {
		int nexty = now.y + diff[i], nextx = now.x + diff[i + 1];
		if (map[nexty][nextx] == '.' && visited[nexty][nextx] == false) {
			//まだ見ていない
			que.push(Point{ nexty , nextx });
			dist[nexty][nextx] = dist[now.y][now.x] + 1;
		}
	}
}
cout << dist[G.y][G.x] << endl;

queの中身がこうなってしまいます。

{(b,6)}
->{(b,5),(c,6)}
->{(c,5),(c,5)}//ん?
->{(c,4),(d,5),(c,4),(d,5)}
->{(d,4),(d,4),(d,4),(d,4)}
->{(e,4),(d,3),(e,4),(d,3),(e,4),(d,3),(e,4),(d,3)}//あれ?

このように指数的に増えていってしまうので、TLEしてしまいます。
なぜこのようになるのかというと、
・(b,5)を見ているとき、(c,5)はまだ行ったことが無いのでqueに追加します
・(c,6)を見ているとき、(c,5)はまだ行ったことが無いのでqueに追加します
という動作になってしまっているからです。

これを解消するには、同じものを二回以上見ないように、「そこはもう調べることになっている」という段階で枝狩りしてやります。

struct Point {
	int y, x;
};
char map[100][100];             //HW '.'通行可、'#'通行不可
bool visited[100][100] = {};    //HW 確認したらtrueに
int  dist[100][100];            //HW Sからの距離

que.push(S);
dist[S.y][S.x] = 0; visited[S.y][S.x] = true;
while (!que.empty()) {
	Point now = que.front(); que.pop();
	const int diff[] = { 1,0,-1,0,1 };
	for (int i = 0; i < 4; ++i) {
		int nexty = now.y + diff[i], nextx = now.x + diff[i + 1];
		if (map[nexty][nextx] == '.' && visited[nexty][nextx] == false) {
			//まだ見ていない
			que.push(Point{ nexty , nextx });
			dist[nexty][nextx] = dist[now.y][now.x] + 1;
			visited[nexty][nextx] = true;
		}
	}
}
cout << dist[G.y][G.x] << endl;

visitedに代入するタイミングを変えただけですね。

セグ木テンプレ

C++11用オレオレセグ木テンプレです。
「変更するコードここから」の下を書き換えて使います。

segment_tree<int, 1000> seg;

で要素int,大きさ1000のセグ木が出来ます。2の累乗には勝手に拡張するので1024でなくて良いです。
これをそのまま使うのではなく、これは一例と思っておいて自分用にカスタマイズするのが良いかと思います。

#include <cstdint>
inline constexpr uint32_t get_min2pow(uint32_t value, uint32_t work = 1) {
	return ((value <= work) ? (work) : (get_min2pow(value, work * 2)));
}
template<typename value_type_, uint32_t N_RAW_MAX>
class segment_tree
{
public:
	using value_type = value_type_;
	static constexpr uint32_t N_MAX = get_min2pow(N_RAW_MAX);
private:
	value_type default_value;
	value_type value[N_MAX * 2 - 1] = {};
	static inline constexpr int32_t getchild(int i) {
		return i * 2 + 1;
	}
	static inline constexpr int32_t getparent(int i) {
		return (i - 1) / 2;
	}
	void Init_impl(int k = 0)
	{
		if (k < N_MAX - 1) {
			//ノード
			auto c1 = getchild(k), c2 = c1 + 1;
			Init_impl(c1);
			Init_impl(c2);
			value[k] = merge(value[c1], value[c2]);
		}
		else {
			//葉
			value[k] = default_value;
		}
	}
	value_type query_impl(int32_t a, int32_t b, int32_t k = 0, int32_t l = 0, int32_t r = N_MAX)const
	{
		if (r <= a || b <= l)return default_value;
		if (a <= l && r <= b)return value[k];
		int m = (l + r) / 2;
		return merge(query_impl(a, b, getchild(k), l, m), query_impl(a, b, getchild(k) + 1, m, r));
	}

public:
	template<typename T, typename FUNC>
	void change(int32_t i, T&& v, FUNC&& operation = std::plus<>{})
	{
		i += N_MAX - 1;
		//葉
		value[i] = std::forward<FUNC>(operation)(std::move(value[i]), std::forward<T>(v));
		i = getparent(i);
		//ノード
		for (;;) {
			auto c1 = getchild(i), c2 = c1 + 1;
			value[i] = merge(value[c1], value[c2]);
			if (i == 0) { break; }
			i = getparent(i);
		}
	}

	//-----------------------------変更するコードここから-----------------------------//
private:
	static inline value_type merge(const value_type& l, const value_type& r)
	{
		ここを書く;
		//RMQ
		return std::min(l, r);
		//RSQ
		return l + r;
}
public:
	inline void init()
	{
		default_value = 例外値を書く;
		//全ての葉にdefault_valueを設定し、親はマージで算出(非効率だけど計算量(N)だし気にしない)
		Init_impl();
	}
	inline value_type query(int32_t a, int32_t b)const
	{
		//デフォルト実装は区間をマージするだけ(たぶんいじることは少ない)
		return query_impl(a, b);
	}
};

情報オリンピック布教用チラシ

学校でプログラミング講習なるものをやっていたので、先生に言って受講生に配らせてもらったチラシです。なので、プログラムが少し書けることを前提に累積和を入れてあります。
デザイン能力が無いのでみんなで改善してね(?)
(配布の際は1,2ページを表面、3,4ページを裏面として、B4で印刷しました)

JOI布教用チラシ(図抜け)

【追記】ちゃんとしたやつをここにあげたのでそっちを見てね。

eiya5498513.hatenablog.jp

 以下元記事...

続きを読む