結果

問題 No.3328 岩井ツリーグラフ
コンテスト
ユーザー elphe
提出日時 2025-10-25 17:51:02
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 26 ms / 2,000 ms
コード長 12,835 bytes
コンパイル時間 2,836 ms
コンパイル使用メモリ 281,300 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-10-25 17:51:08
合計ジャッジ時間 5,163 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

namespace MyLib
{
	template<uint_fast32_t MOD> class mod_int
	{
	private:
		uint_fast32_t value = 0;
		[[nodiscard]] static inline constexpr bool is_prime(const uint_fast32_t arg) noexcept
		{
			for (uint_fast32_t i = 2; i * i <= arg; ++i)
				if (arg % i == 0) [[unlikely]] return false;
			return true;
		}
		[[nodiscard]] static inline constexpr uint_fast32_t pow_mod(uint_fast32_t a, size_t b) noexcept
		{
			if constexpr (MOD == 1) return 0;
			uint_fast32_t ans = 1;
			a %= MOD;
			for (; b != 0; b >>= 1, a = static_cast<uint_fast64_t>(a) * a % MOD)
				if (b & 1) ans = ans * static_cast<uint_fast64_t>(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 = (uint_fast32_t)(arg % MOD); }
	
		[[nodiscard]] constexpr mod_int<MOD> operator+() const noexcept { return mod_int<MOD>(value); }
		[[nodiscard]] constexpr mod_int<MOD> operator-() const noexcept { [[assume(value < MOD)]]; return mod_int<MOD>(value == 0 ? 0 : MOD - value); }
	
		[[nodiscard]] friend constexpr mod_int<MOD> operator+(const mod_int<MOD> mi1, const mod_int<MOD> mi2) noexcept { [[assume(mi1.value < MOD && mi2.value < MOD)]]; return mod_int<MOD>(mi1.value >= MOD - mi2.value ? mi1.value - (MOD - mi2.value) : mi1.value + mi2.value); }
		[[nodiscard]] friend constexpr mod_int<MOD> operator-(const mod_int<MOD> mi1, const mod_int<MOD> mi2) noexcept { [[assume(mi1.value < MOD && mi2.value < MOD)]]; return mod_int<MOD>(mi1.value >= mi2.value ? mi1.value - mi2.value : MOD - (mi2.value - mi1.value)); }
		[[nodiscard]] friend constexpr mod_int<MOD> operator*(const mod_int<MOD> mi1, const mod_int<MOD> mi2) noexcept { [[assume(mi1.value < MOD && mi2.value < MOD)]]; if constexpr (MOD >= (1u << 16)) return mod_int<MOD>(static_cast<uint_fast64_t>(mi1.value) * mi2.value % MOD); else return mod_int<MOD>(mi1.value * mi2.value % MOD); }
		[[nodiscard]] friend constexpr mod_int<MOD> operator/(const mod_int<MOD> mi1, const mod_int<MOD> mi2) noexcept { [[assume(mi1.value < MOD && mi2.value < MOD)]]; static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if constexpr (MOD >= (1u << 16)) return mod_int<MOD>(static_cast<uint_fast64_t>(mi1.value) * pow_mod(mi2.value, MOD - 2) % MOD); else return mod_int<MOD>(mi1.value * pow_mod(mi2.value, MOD - 2) % MOD); }
		template<typename T> [[nodiscard]] friend constexpr mod_int<MOD> operator+(const mod_int<MOD> mi, T arg) noexcept { [[assume(mi.value < MOD)]]; arg %= MOD; return mod_int<MOD>(mi.value >= MOD - static_cast<uint_fast32_t>(arg) ? mi.value - (MOD - static_cast<uint_fast32_t>(arg)) : mi.value + static_cast<uint_fast32_t>(arg)); }
		template<typename T> [[nodiscard]] friend constexpr mod_int<MOD> operator-(const mod_int<MOD> mi, T arg) noexcept { [[assume(mi.value < MOD)]]; arg %= MOD; return mod_int<MOD>(mi.value >= static_cast<uint_fast32_t>(arg) ? mi.value - static_cast<uint_fast32_t>(arg) : MOD - (static_cast<uint_fast32_t>(arg) - mi.value)); }
		template<typename T> [[nodiscard]] friend constexpr mod_int<MOD> operator*(const mod_int<MOD> mi, const T arg) noexcept { [[assume(mi.value < MOD)]]; if constexpr (MOD >= (1u << 16)) return mod_int<MOD>(static_cast<uint_fast64_t>(mi.value) * (arg % MOD) % MOD); else return mod_int<MOD>(mi.value * static_cast<uint_fast32_t>(arg % MOD) % MOD); }
		template<typename T> [[nodiscard]] friend constexpr mod_int<MOD> operator/(const mod_int<MOD> mi, const T arg) noexcept { [[assume(mi.value < MOD)]]; static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if constexpr (MOD >= (1u << 16)) return mod_int<MOD>(static_cast<uint_fast64_t>(mi.value) * pow_mod(static_cast<uint_fast32_t>(arg % MOD), MOD - 2) % MOD); else return mod_int<MOD>(mi.value * pow_mod(static_cast<uint_fast32_t>(arg % MOD), MOD - 2) % MOD); }
		template<typename T> [[nodiscard]] friend constexpr mod_int<MOD> operator+(T arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return mi + arg; }
		template<typename T> [[nodiscard]] friend constexpr mod_int<MOD> operator-(T arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return (-mi) + arg; }
		template<typename T> [[nodiscard]] friend constexpr mod_int<MOD> operator*(const T arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return mi * arg; }
		template<typename T> [[nodiscard]] friend constexpr mod_int<MOD> operator/(const T arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return mi.pow_mod(MOD - 2) * arg; }
	
		constexpr mod_int<MOD>& operator+=(const mod_int<MOD> other) noexcept { [[assume(value < MOD && other.value < MOD)]]; if (value >= MOD - other.value) value -= (MOD - other.value); else value += other.value; return *this; }
		constexpr mod_int<MOD>& operator-=(const mod_int<MOD> other) noexcept { [[assume(value < MOD && other.value < MOD)]]; if (value >= other.value) value -= other.value; else value += (MOD - other.value); return *this; }
		constexpr mod_int<MOD>& operator*=(const mod_int<MOD> other) noexcept { [[assume(value < MOD && other.value < MOD)]]; if constexpr (MOD >= (1u << 16)) value = static_cast<uint_fast64_t>(value) * other.value % MOD; else value = value * other.value % MOD; return *this; }
		constexpr mod_int<MOD>& operator/=(const mod_int<MOD> other) noexcept { [[assume(value < MOD && other.value < MOD)]]; static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if constexpr (MOD >= (1u << 16)) value = static_cast<uint_fast64_t>(value) * pow_mod(other.value, MOD - 2) % MOD; else value = value * pow_mod(other.value, MOD - 2) % MOD; return *this; }
		template<typename T> constexpr mod_int<MOD>& operator+=(T arg) noexcept { [[assume(value < MOD)]]; 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 { [[assume(value < MOD)]]; arg %= MOD; if (value >= arg) value -= arg; else value += (MOD - arg); return *this; }
		template<typename T> constexpr mod_int<MOD>& operator*=(const T arg) noexcept { [[assume(value < MOD)]]; if constexpr (MOD >= (1u << 16)) value = static_cast<uint_fast64_t>(value) * (arg % MOD) % MOD; else value = value * (arg % MOD) % MOD; return *this; }
		template<typename T> constexpr mod_int<MOD>& operator/=(const T arg) noexcept { [[assume(value < MOD)]]; static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if constexpr (MOD >= (1u << 16)) value = static_cast<uint_fast64_t>(value) * pow_mod(static_cast<uint_fast32_t>(arg % MOD), MOD - 2) % MOD; else value = value * pow_mod(static_cast<uint_fast32_t>(arg % MOD), MOD - 2) % MOD; return *this; }
		template<typename T> friend constexpr T& operator+=(T& arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return arg += mi.value; }
		template<typename T> friend constexpr T& operator-=(T& arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return arg -= mi.value; }
		template<typename T> friend constexpr T& operator*=(T& arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return arg *= mi.value; }
		template<typename T> friend constexpr T& operator/=(T& arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return arg /= mi.value; }
	
		constexpr mod_int<MOD>& operator++() noexcept { [[assume(value < MOD)]]; if (value + 1 == MOD) [[unlikely]] value = 0; else ++value; return *this; }
		constexpr mod_int<MOD> operator++(int) noexcept { [[assume(value < MOD)]]; const auto temp = value; if (value + 1 == MOD) [[unlikely]] value = 0; else ++value; return mod_int<MOD>(temp); }
		constexpr mod_int<MOD>& operator--() noexcept { [[assume(value < MOD)]]; if (value == 0) [[unlikely]] value = MOD - 1; else --value; return *this; }
		constexpr mod_int<MOD> operator--(int) noexcept { [[assume(value < MOD)]]; const auto temp = value; if (value == 0) [[unlikely]] value = MOD - 1; else --value; return *this; }
	
		[[nodiscard]] friend constexpr bool operator==(const mod_int<MOD> mi1, const mod_int<MOD> mi2) noexcept { [[assume(mi1.value < MOD && mi2.value < MOD)]]; return mi1.value == mi2.value; }
		[[nodiscard]] friend constexpr bool operator!=(const mod_int<MOD> mi1, const mod_int<MOD> mi2) noexcept { [[assume(mi1.value < MOD && mi2.value < MOD)]]; return mi1.value != mi2.value; }
		[[nodiscard]] friend constexpr bool operator<(const mod_int<MOD> mi1, const mod_int<MOD> mi2) noexcept { [[assume(mi1.value < MOD && mi2.value < MOD)]]; return mi1.value < mi2.value; }
		[[nodiscard]] friend constexpr bool operator<=(const mod_int<MOD> mi1, const mod_int<MOD> mi2) noexcept { [[assume(mi1.value < MOD && mi2.value < MOD)]]; return mi1.value <= mi2.value; }
		[[nodiscard]] friend constexpr bool operator>(const mod_int<MOD> mi1, const mod_int<MOD> mi2) noexcept { [[assume(mi1.value < MOD && mi2.value < MOD)]]; return mi1.value > mi2.value; }
		[[nodiscard]] friend constexpr bool operator>=(const mod_int<MOD> mi1, const mod_int<MOD> mi2) noexcept { [[assume(mi1.value < MOD && mi2.value < MOD)]]; return mi1.value >= mi2.value; }
		template<typename T> [[nodiscard]] friend constexpr bool operator==(const mod_int<MOD> mi, const T arg) noexcept { [[assume(mi.value < MOD)]]; static_assert(std::is_integral<T>::value, "T is not an integral type."); return mi.value == arg; }
		template<typename T> [[nodiscard]] friend constexpr bool operator!=(const mod_int<MOD> mi, const T arg) noexcept { [[assume(mi.value < MOD)]]; static_assert(std::is_integral<T>::value, "T is not an integral type."); return mi.value != arg; }
		template<typename T> [[nodiscard]] friend constexpr bool operator<(const mod_int<MOD> mi, const T arg) noexcept { [[assume(mi.value < MOD)]]; static_assert(std::is_integral<T>::value, "T is not an integral type."); return mi.value < arg; }
		template<typename T> [[nodiscard]] friend constexpr bool operator<=(const mod_int<MOD> mi, const T arg) noexcept { [[assume(mi.value < MOD)]]; static_assert(std::is_integral<T>::value, "T is not an integral type."); return mi.value <= arg; }
		template<typename T> [[nodiscard]] friend constexpr bool operator>(const mod_int<MOD> mi, const T arg) noexcept { [[assume(mi.value < MOD)]]; static_assert(std::is_integral<T>::value, "T is not an integral type."); return mi.value > arg; }
		template<typename T> [[nodiscard]] friend constexpr bool operator>=(const mod_int<MOD> mi, const T arg) noexcept { [[assume(mi.value < MOD)]]; static_assert(std::is_integral<T>::value, "T is not an integral type."); return mi.value >= arg; }
		template<typename T> [[nodiscard]] friend constexpr bool operator==(const T arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return mi == arg; }
		template<typename T> [[nodiscard]] friend constexpr bool operator!=(const T arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return mi != arg; }
		template<typename T> [[nodiscard]] friend constexpr bool operator<(const T arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return mi > arg; }
		template<typename T> [[nodiscard]] friend constexpr bool operator<=(const T arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return mi >= arg; }
		template<typename T> [[nodiscard]] friend constexpr bool operator>(const T arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return mi < arg; }
		template<typename T> [[nodiscard]] friend constexpr bool operator>=(const T arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return mi <= arg; }
	
		[[nodiscard]] constexpr operator unsigned int() const noexcept { [[assume(value < MOD)]]; return this->value; }
	
		[[nodiscard]] constexpr mod_int<MOD> pow_mod(uint_fast64_t times) const noexcept
		{
			[[assume(value < MOD)]];
			if constexpr (MOD == 1) return 0;
			mod_int<MOD> ans = 1, a = value;
			for (; times != 0; times >>= 1, a *= a)
				if (times & 1) ans *= a;
	
			return ans;
		}
	};
}

template<uint_fast32_t MOD>
[[nodiscard]] static inline constexpr uint_fast32_t solve([[maybe_unused]] const uint_least32_t X, const std::vector<uint_least32_t>& Y) noexcept
{
	MyLib::mod_int<MOD> ans = 0;
	const MyLib::mod_int<MOD> sum_Y = std::accumulate(Y.begin(), Y.end(), MyLib::mod_int<MOD>(0));
	constexpr MyLib::mod_int<MOD> half = MyLib::mod_int<MOD>(1) / 2, one_of_six = MyLib::mod_int<MOD>(1) / 6;
	for (const MyLib::mod_int<MOD> y : Y) ans += y * (y + 1) * ((y + 1) * half - (y * 2 + 1) * one_of_six + (sum_Y - y) * half);

	return ans;
}

int main()
{
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);
	
	uint_fast32_t X;
	std::cin >> X;
	std::vector<uint_least32_t> Y(X);
	for (auto& y : Y) std::cin >> y;

	std::cout << solve<998244353>(X, Y) << '\n';
	return 0;
}
0