結果

問題 No.314 ケンケンパ
ユーザー elpheelphe
提出日時 2024-12-10 17:00:07
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 7 ms / 1,000 ms
コード長 7,944 bytes
コンパイル時間 678 ms
コンパイル使用メモリ 69,300 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-10 17:00:09
合計ジャッジ時間 1,793 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
6,816 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 1 ms
6,816 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 2 ms
6,816 KB
testcase_07 AC 2 ms
6,820 KB
testcase_08 AC 2 ms
6,816 KB
testcase_09 AC 2 ms
6,820 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,816 KB
testcase_14 AC 2 ms
6,816 KB
testcase_15 AC 2 ms
6,816 KB
testcase_16 AC 2 ms
6,816 KB
testcase_17 AC 2 ms
6,816 KB
testcase_18 AC 4 ms
6,816 KB
testcase_19 AC 6 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdint>
#include <array>

using namespace std;

template<unsigned int MOD> class mod_int
{
private:
	unsigned int value = 0;
	constexpr static bool is_prime(const unsigned int arg) noexcept
	{
		for (unsigned int i = 2; i * i <= arg; ++i)
			if (arg % i == 0) return false;
		return true;
	}
	constexpr static unsigned int pow_mod(unsigned int a, size_t b) noexcept
	{
		if (MOD == 1) return 0;
		unsigned int ans = 1;
		a %= MOD;
		for (; b != 0; b >>= 1, a = static_cast<unsigned long long>(a) * a % MOD)
			if (b & 1) ans = ans * static_cast<unsigned long long>(a) % MOD;

		return ans;
	}

public:
	constexpr mod_int() noexcept { static_assert(MOD != 0, "0 cannot be set as \'MOD.\'"); }
	template<typename T> constexpr mod_int(const T arg) noexcept { static_assert(MOD != 0, "0 cannot be set as \'MOD.\'"); value = (unsigned int)(arg % MOD); }

	constexpr mod_int<MOD> operator+(const mod_int<MOD> other) const noexcept { return mod_int(this->value >= MOD - other.value ? this->value - (MOD - other.value) : this->value + other.value); }
	constexpr mod_int<MOD> operator-(const mod_int<MOD> other) const noexcept { return mod_int(this->value >= other.value ? this->value - other.value : MOD - (other.value - this->value)); }
	constexpr mod_int<MOD> operator*(const mod_int<MOD> other) const noexcept { if constexpr (MOD >= (1u << 16)) return mod_int(static_cast<unsigned long long>(this->value) * other.value % MOD); else return mod_int(this->value * other.value % MOD); }
	constexpr mod_int<MOD> operator/(const mod_int<MOD> other) const noexcept { static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if constexpr (MOD >= (1u << 16)) return mod_int(static_cast<unsigned long long>(this->value) * pow_mod(other.value, MOD - 2) % MOD); else return mod_int(this->value * pow_mod(other.value, MOD - 2) % MOD); }
	template<typename T> constexpr mod_int<MOD> operator+(T arg) const noexcept { arg %= MOD; return mod_int(value >= MOD - static_cast<unsigned int>(arg) ? value - (MOD - static_cast<unsigned int>(arg)) : value + static_cast<unsigned int>(arg)); }
	template<typename T> constexpr mod_int<MOD> operator-(T arg) const noexcept { arg %= MOD; return mod_int(value >= static_cast<unsigned int>(arg) ? value - static_cast<unsigned int>(arg) : MOD - (static_cast<unsigned int>(arg) - value)); }
	template<typename T> constexpr mod_int<MOD> operator*(T arg) const noexcept { if constexpr (MOD >= (1u << 16)) return mod_int(static_cast<unsigned long long>(value) * (arg % MOD) % MOD); else return mod_int(value * static_cast<unsigned int>(arg % MOD) % MOD); }
	template<typename T> constexpr mod_int<MOD> operator/(T arg) const noexcept { static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if constexpr (MOD >= (1u << 16)) return mod_int(static_cast<unsigned long long>(value) * pow_mod(static_cast<unsigned int>(arg % MOD), MOD - 2) % MOD); else return mod_int(value * pow_mod(static_cast<unsigned int>(arg % MOD), MOD - 2) % MOD); }

	constexpr mod_int<MOD>& operator+=(const mod_int<MOD> other) noexcept { if (this->value >= MOD - other.value) this->value -= (MOD - other.value); else this->value += other.value; return *this; }
	constexpr mod_int<MOD>& operator-=(const mod_int<MOD> other) noexcept { if (this->value >= other.value) this->value -= other.value; else this->value += (MOD - other.value); return *this; }
	constexpr mod_int<MOD>& operator*=(const mod_int<MOD> other) noexcept { if constexpr (MOD >= (1u << 16)) this->value = static_cast<unsigned long long>(this->value) * other.value % MOD; else this->value = this->value * other.value % MOD; return *this; }
	constexpr mod_int<MOD>& operator/=(const mod_int<MOD> other) noexcept { static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if constexpr (MOD >= (1u << 16)) this->value = static_cast<unsigned long long>(this->value) * pow_mod(other.value, MOD - 2) % MOD; else this->value = this->value * pow_mod(other.value, MOD - 2) % MOD; return *this; }
	template<typename T> constexpr mod_int<MOD>& operator+=(T arg) noexcept { arg %= MOD; if (value >= MOD - arg) value -= (MOD - arg); else value += arg; return *this; }
	template<typename T> constexpr mod_int<MOD>& operator-=(T arg) noexcept { arg %= MOD; if (value >= arg) value -= arg; else value += (MOD - arg); return *this; }
	template<typename T> constexpr mod_int<MOD>& operator*=(T arg) noexcept { if constexpr (MOD >= (1u << 16)) value = static_cast<unsigned long long>(value) * (arg % MOD) % MOD; else value = value * (arg % MOD) % MOD; return *this; }
	template<typename T> constexpr mod_int<MOD>& operator/=(T arg) noexcept { static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if constexpr (MOD >= (1u << 16)) value = static_cast<unsigned long long>(value) * pow_mod(static_cast<unsigned int>(arg % MOD), MOD - 2) % MOD; else value = value * pow_mod(static_cast<unsigned int>(arg % MOD), MOD - 2) % MOD; return *this; }

	constexpr mod_int<MOD>& operator++() noexcept { if (value + 1 == MOD) value = 0; else ++value; return *this; }
	constexpr mod_int<MOD> operator++(int) noexcept { const auto temp = value; if (value + 1 == MOD) value = 0; else ++value; return mod_int<MOD>(temp); }
	constexpr mod_int<MOD>& operator--() noexcept { if (value == 0) value = MOD - 1; else --value; return *this; }
	constexpr mod_int<MOD> operator--(int) noexcept { const auto temp = value; if (value == 0) value = MOD - 1; else --value; return *this; }

	constexpr bool operator==(const mod_int<MOD> other) const noexcept { return this->value == other.value; }
	constexpr bool operator!=(const mod_int<MOD> other) const noexcept { return this->value != other.value; }
	constexpr bool operator<(const mod_int<MOD> other) const noexcept { return this->value < other.value; }
	constexpr bool operator<=(const mod_int<MOD> other) const noexcept { return this->value <= other.value; }
	constexpr bool operator>(const mod_int<MOD> other) const noexcept { return this->value > other.value; }
	constexpr bool operator>=(const mod_int<MOD> other) const noexcept { return this->value >= other.value; }
	template<typename T> constexpr bool operator==(const T arg) const noexcept { static_assert(is_integral<T>::value, "T is not an integral type."); return value == arg; }
	template<typename T> constexpr bool operator!=(const T arg) const noexcept { static_assert(is_integral<T>::value, "T is not an integral type."); return value != arg; }
	template<typename T> constexpr bool operator<(const T arg) const noexcept { static_assert(is_integral<T>::value, "T is not an integral type."); return value < arg; }
	template<typename T> constexpr bool operator<=(const T arg) const noexcept { static_assert(is_integral<T>::value, "T is not an integral type."); return value <= arg; }
	template<typename T> constexpr bool operator>(const T arg) const noexcept { static_assert(is_integral<T>::value, "T is not an integral type."); return value > arg; }
	template<typename T> constexpr bool operator>=(const T arg) const noexcept { static_assert(is_integral<T>::value, "T is not an integral type."); return value >= arg; }

	operator unsigned int() const noexcept { return this->value; }

	constexpr mod_int<MOD> pow_mod(unsigned long long times)
	{
		if (MOD == 1) return 0;
		mod_int<MOD> ans = 1;
		unsigned int a = this->value;
		for (; times != 0; times >>= 1, a = static_cast<unsigned long long>(a) * a % MOD)
			if (times & 1) ans.value = static_cast<unsigned long long>(ans.value) * a % MOD;

		return ans;
	}
};

int main()
{
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	uint32_t N, i;
	cin >> N;

	if (N == 1)
	{
		cout << "1\n";
		return 0;
	}

	array<mod_int<1'000'000'007>, 3> dp_cur, dp_prev;
	dp_cur[0] = dp_cur[1] = 1, dp_cur[2] = 0;
	for (i = 2; i != N; ++i)
	{
		dp_cur.swap(dp_prev);

		dp_cur[0] = dp_prev[2];
		dp_cur[1] = dp_prev[0] + dp_prev[2];
		dp_cur[2] = dp_prev[1];
	}

	cout << dp_cur[0] + dp_cur[1] + dp_cur[2] << '\n';
	return 0;
}
0